Artifact Content
Not logged in

Artifact 9574f58423d9446614706ac9f7bc0b8024367ec4


#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <cstring>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;

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) 
	{
		// input
		vector<LL> rt(N), ft(N);
		{
			rt[0] = roadFirst % roadMod;
			for(int i=1; i<N; ++i)
				rt[i] = (LL(rt[i-1])*roadProd + roadAdd) % roadMod;
		}
		{
			ft[0] = flightFirst % flightMod;
			for(int i=1; i<N; ++i)
				ft[i] = (LL(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;
			}
			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;
	}
};

// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
 { os << "{ ";
   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const long long& Expected, const long long& Received) {
 bool ok = (Expected == Received);
 if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END	 verify_case(_, RoadOrFlightHard().minTime(N, roadFirst, roadProd, roadAdd, roadMod, flightFirst, flightProd, flightAdd, flightMod, K));}
int main(){

CASE(0)
	int N = 3; 
	int roadFirst = 14; 
	int roadProd = 1; 
	int roadAdd = 2; 
	int roadMod = 10; 
	int flightFirst = 18; 
	int flightProd = 1; 
	int flightAdd = 10; 
	int flightMod = 17; 
	int K = 1; 
	long long _ = 14LL; 
END
CASE(1)
	int N = 3; 
	int roadFirst = 4; 
	int roadProd = 1; 
	int roadAdd = 2; 
	int roadMod = 10; 
	int flightFirst = 1; 
	int flightProd = 1; 
	int flightAdd = 10; 
	int flightMod = 17; 
	int K = 2; 
	long long _ = 11LL; 
END
CASE(2)
	int N = 3; 
	int roadFirst = 4; 
	int roadProd = 1; 
	int roadAdd = 2; 
	int roadMod = 10; 
	int flightFirst = 1; 
	int flightProd = 1; 
	int flightAdd = 6; 
	int flightMod = 9; 
	int K = 1; 
	long long _ = 12LL; 
END
CASE(3)
	int N = 5; 
	int roadFirst = 85739; 
	int roadProd = 94847; 
	int roadAdd = 93893; 
	int roadMod = 98392; 
	int flightFirst = 92840; 
	int flightProd = 93802; 
	int flightAdd = 93830; 
	int flightMod = 92790; 
	int K = 3; 
	long long _ = 122365LL; 
END
CASE(4)
	int N = 1; 
	int roadFirst = 2; 
	int roadProd = 1; 
	int roadAdd = 1; 
	int roadMod = 100; 
	int flightFirst = 1; 
	int flightProd = 1; 
	int flightAdd = 1; 
	int flightMod = 2; 
	int K = 0; 
	long long _ = 2LL; 
END
CASE(4)
	int N = 1; 
	int roadFirst = 2; 
	int roadProd = 1; 
	int roadAdd = 1; 
	int roadMod = 100; 
	int flightFirst = 1; 
	int flightProd = 1; 
	int flightAdd = 1; 
	int flightMod = 2; 
	int K = 1; 
	long long _ = 1LL; 
END
CASE(5)
	int N = 1; 
	int roadFirst = 0; 
	int roadProd = 1; 
	int roadAdd = 1; 
	int roadMod = 100; 
	int flightFirst = 0; 
	int flightProd = 1; 
	int flightAdd = 1; 
	int flightMod = 1; 
	int K = 1; 
	long long _ = 0LL; 
END
CASE(6)
	int N = 400000; 
	int roadFirst = 1234; 
	int roadProd = 56789; 
	int roadAdd = 32323; 
	int roadMod = 99999; 
	int flightFirst = 9876; 
	int flightProd = 44344; 
	int flightAdd = 7865; 
	int flightMod = 99999; 
	int K = 40; 
	long long _ = -1LL; 
END

}
// END CUT HERE