Codeforces ECR #074 : G. Adilbek and the Watering System

これは典型な気がするなぁ。
https://codeforces.com/contest/1238/problem/G

問題

水がCリットル入る放水機があり、初期状態でC0リットル入っている。
この放水機を計M分動かすことを考える。放水機は1分に1リットルの水を流す。

放水機の初期状態の水量ではM分持たないかもしれない。
ここでN人の人がいる。各人T[i]分目にやってきて、最大A[i]リットルまで水を補給してもらうことができる。
ただし1リットル当たりB[i]のお金がかかる。

放水をM分継続させるための水をキープする場合、最小でどの程度お金がかかるか。

解法

これは典型で、とりあえず補給可能な水を金額の安い順にプールしておき、時間経過とともに消費させておく。
ただしプール量がCを超える分は適宜捨てる。

int Q;
int N,M,C,C0;
int T[505050],A[505050],B[505050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&Q);
	while(Q--) {
		scanf("%d%d%d%d",&N,&M,&C,&C0);
		vector<vector<int>> ev;
		FOR(i,N) {
			scanf("%d%d%d",&T[i],&A[i],&B[i]);
			ev.push_back({T[i],B[i],i});
		}
		T[N]=0,A[N]=C0,B[N]=0;
		ev.push_back({M,0});
		sort(ALL(ev));
		int ct=0;
		ll ret=0;
		set<pair<int,int>> S;
		S.insert({0,N});
		int TL=C0;
		
		FORR(e,ev) {
			int t=e[0]-ct;
			TL-=t;
			ct=e[0];
			while(t) {
				if(S.empty()) {
					ret=-1;
					break;
				}
				auto it=S.begin();
				x=it->second;
				y=min(t,A[x]);
				ret+=1LL*B[x]*y;
				A[x]-=y;
				t-=y;
				if(A[x]==0) S.erase(S.begin());
			}
			if(ct==M || ret==-1) break;
			S.insert({B[e[2]],e[2]});
			TL+=A[e[2]];
			while(TL>C) {
				auto it=*S.rbegin();
				x=it.second;
				y=min(A[x],TL-C);
				A[x]-=y;
				TL-=y;
				if(A[x]) break;
				S.erase(it);
				
			}
			
		}
		
		cout<<ret<<endl;
	}
}

まとめ

普段ならDiv1のB～Cで出そうな問題だが、なぜECRの最終問題に…。