cafelier@SRM

SRM468 500

あとで | 00:08 |

DPテンプレート改を投入

typedef long long LL;

template<typename T>
struct DP3x
{
   int N1, N2, N3;
   vector<T> data;
   DP3x(int, int N2, int N3, const T& t = T())
      : N1(2), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()*sizeof(T) < (1<<26)); }
   T& operator()(int i1, int i2, int i3)
      { i1&=1; return data[ ((i1*N2)+i2)*N3+i3 ]; }
   void swap(DP3x& rhs)
      { data.swap(rhs.data); }
};

static const LL inf = (1LL << 60);

class RoadOrFlightHard { public:
   long long minTime(int N, int roadFirst, int roadProd, int roadAdd, int roadMod,
                     int flightFirst, int flightProd, int flightAdd, int flightMod, int K) 
   {
      vector<LL> rt(N), ft(N);
      {
         rt[0] = roadFirst % roadMod;
         for(int i=1; i<N; ++i)
            rt[i] = (rt[i-1]*roadProd + roadAdd) % roadMod;

         ft[0] = flightFirst % flightMod;
         for(int i=1; i<N; ++i)
            ft[i] = (ft[i-1]*flightProd + flightAdd) % flightMod;
      }

      DP3x<LL> dp(N+1, K+1, 2);
      for(int n=0; n<=N; ++n)
      for(int k=0; k<=K; ++k)
         if( n == 0 ) {
            dp(n,k,0) = 0;
            dp(n,k,1) = inf; // ※追記：この行抜けてた。酷い。MLE以前の問題だ…
         }
         else {
            dp(n,k,0) = min(dp(n-1,k,0), dp(n-1,k,1)) + rt[n-1];
            if( k == 0 )
               dp(n,k,1) = inf;
            else
               dp(n,k,1) = min(dp(n-1,k,1), dp(n-1,k-1,0)) + ft[n-1];
         }

      LL ans = inf;
      for(int k=0; k<=K; ++k)
         ans = min(ans, min(dp(N,k,0), dp(N,k,1)));
      return ans;
   }
};