TopCoder SRM 742 Div1 Hard Depot

落としておいてなんだけど、これ900ptでも良くないか。
https://community.topcoder.com/stat?c=problem_statement&pm=15152

問題

港にいくつか荷物が届くことを考える。
「D日目から初めてI日毎に計M回まで体積Sの荷物が1個届く」という情報がN個与えられる。

これとは別に、クエリとして「D日目に体積Sまで荷物を詰める船が出港する」という条件が与えられる。
各クエリに対し、1～D日目の間に港に届いた荷物の部分集合のうち体積総和がちょうどSになるものがあるか判定せよ。
なお、各クエリは独立であり、クエリ処理の結果荷物が減ることはない。

解法

Sの上限が300,000と小さいのがミソ。
元の情報に対し、以下を求めてしまおう。
f(S') := 体積の総和がS'となるような荷物の部分集合が存在する最初の日にち
g(S') := f(S')の状態を成立させる際、ちょうど体積の総和がS'になる際に追加された荷物情報の最小値

f(S')がわかっているとき、i番目の情報よりf(S')より後の日付(ただしi＞g(S')ならf(S')と同一日でもよい)に荷物が来るなら、f(S'+S)およびg(S'+S)を更新できる。
よってこれらはO(NS)で埋めることができる。
f(S)が求められれば、各クエリはO(1)で回答可能。

int N;
ll MD[305050];
int mi[305050];
ll D[21],S[21],M[21],I[21];

class Depot {
	public:
	vector<int> split_int(const string &str, char delim=' '){
		vector<int> res;
		size_t current = 0, found;
		while((found = str.find_first_of(delim, current)) != string::npos){
			string s = string(str, current, found - current);
			res.push_back(stoi(s));
			current = found + 1;
		}
		string s = string(str, current, str.size() - current);
		res.push_back(stoi(s));
		return res;
	}
	
	int countPositive(vector <string> arrivals, vector <string> queries) {
		N=arrivals.size();
		int i,j,x;
		
		ZERO(mi);
		FOR(i,305000) MD[i]=1LL<<60;
		MD[0]=0;
		mi[0]=-1;
		FOR(i,N) {
			auto v=split_int(arrivals[i]);
			D[i]=v[0];
			I[i]=v[1];
			M[i]=v[2];
			S[i]=v[3];
		}
		FOR(j,304000) {
			FOR(i,N) {
				ll nex=MD[j]+(i<=mi[j]);
				nex=max(nex,D[i]);
				nex=D[i]+(nex-D[i]+I[i]-1)/I[i]*I[i];
				if(nex>D[i]+(M[i]-1)*I[i] || j+S[i]>300000) continue;
				if(MD[j+S[i]]>nex) {
					MD[j+S[i]]=nex;
					mi[j+S[i]]=i;
				}
				if(MD[j+S[i]]==nex) mi[j+S[i]]=min(mi[j+S[i]],i);
			}
		}
		
		int ret=0;
		FORR(q,queries) {
			auto v=split_int(q);
			if(v.size()==2) {
				ret+=MD[v[1]]<=v[0];
			}
			else {
				ll d=v[0];
				ll s=v[1];
				ll A1=v[2];
				ll B1=v[3];
				ll A2=v[4];
				ll B2=v[5];
				int Q=v[6];
				FOR(i,Q) {
					ret+=MD[(s+i*A2-1)%B2+1]<=(d+i*A1-1)%B1+1;
				}
			}
		}
		return ret;
	}
}

まとめ

入力ひどすぎでしょ。