Codeforces ECR #145 : E. Two Tanks

ここら辺からまぁまぁ苦戦してるな。
https://codeforces.com/contest/1809/problem/E

問題

Aリットル入るタンクとBリットル入るタンクがある。
ここにN個の処理が指定される。

これは片方のタンクからもう片方にタンクに指定された量の水をうつす処理である。
ただし、指定量の水をうつすと、水が足りなかったり溢れる場合は、それらが生じないよう移す量を減らす。
両タンクの初期量の各パターンにおいて、それぞれ最終的に両タンクにどれだけの水が入った状態となるか。

解法

水の総量が同じパターンをまとめて処理しよう。
この時、前者のタンクの初期水量に応じて、各処理の後の前者のタンクの水量は、傾き0と1の線を高々3つ合わせた形になるので、それらが処理毎にどう遷移するか計算していこう。

int N,A,B;
int V[10101];

int ret[1010][1010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>A>>B;
	FOR(i,N) cin>>V[i];
	for(i=0;i<=A+B;i++) {
		int f=100000;
		deque<int> Q;
		vector<pair<int,int>> cand;
		for(x=0;x<=A;x++) {
			y=i-x;
			if(y>=0&&y<=B) {
				cand.push_back({x,y});
				f=min(f,x);
				Q.push_back(1);
			}
		}
		if(Q.empty()) continue;
		int mi=max(0,i-B);
		int ma=min(A,i);
		FOR(j,N) {
			if(V[j]>0) {
				f-=V[j];
				while(f<mi&&Q.size()>1) {
					f++;
					x=Q[0];
					Q.pop_front();
					Q[0]+=x;
				}
				if(f<mi) f=mi;
			}
			else {
				f-=V[j];
				while(f+Q.size()-1>ma&&Q.size()>1) {
					x=Q.back();
					Q.pop_back();
					Q.back()+=x;
				}
				if(f+Q.size()-1>ma) f=ma-(Q.size()-1);
			}
		}
		reverse(ALL(cand));
		FOR(x,Q.size()) while(Q[x]) {
			ret[cand.back().first][cand.back().second]=f+x;
			Q[x]--;
			cand.pop_back();
		}
		assert(cand.empty());
	}
	
	FOR(y,A+1) {
		FOR(x,B+1) cout<<ret[y][x]<<" ";
		cout<<endl;
	}
	
}

まとめ

思いついてしまえばそこまで難しくないね。