Codeforces #437 Div1 B. Ordering Pizza

しょうもないミス。
http://codeforces.com/contest/866/problem/B

問題

A,B２種類のピザがある。
それぞれ１枚当たりS切れで構成される。

ここにN人の人がいる。
各人、欲しいピザの量s[i]切れと、A,B両ピザ1切れあたりの満足度a[i],b[i]が与えられる。
s[i]切れは種類のピザが混在していても構わない。

さて、ここで全員に欲しい分のピザがいきわたるようピザを購入することを考える。
ピザは１枚単位で購入でき、両ピザの枚数の総和は最小でなければならない。
最適なピザの購入と配分をしたとき、満足度の総和を求めよ。

解法

基本的に、a[i]≧b[i]な人はA、b[i]＞a[i]な人にはBのピザがいきわたるのが良い。
よってN人の人を両者に分類し、その差でソートしよう。
差が大きい人ほど、好みのピザを選んだ時の満足度の上昇が大きいので優先的に好みのピザを与える。
A,Bそれぞれのグループでにおけるピザの総量をSa,Sbとしたとき、A,Bのピザをfloow(Sa/S)、floow(Sb/S)毎ずつ買い、そのように分け与えていこう。

そうすると、残る両グループの必要ピザ数はどちらもS切れ以下なので、あと最大で2枚ピザを買えば全員にいきわたる。
これは２枚のピザの買い方を全通り試せばよい。

int N,S;
ll V[101010],A[101010],B[101010],V2[101010];
ll sum[3];
vector<pair<int,int>> T[3];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>N>>S;
	ll ret=0;
	FOR(i,N) {
		cin>>V[i]>>A[i]>>B[i];
		if(A[i]>=B[i]) T[0].push_back({A[i]-B[i],i}), sum[0]+=V[i];
		if(A[i]<B[i]) T[1].push_back({B[i]-A[i],i}), sum[1]+=V[i];
	}
	
	FOR(i,2) {
		sort(ALL(T[i]));
		ll left=sum[i]/S*S;
		sum[i]-=left;
		while(left>0) {
			x=T[i].back().second;
			ll del=min(left,V[x]);
			if(i<1) ret+=del*A[x];
			else ret+=del*B[x];
			
			V[x]-=del;
			left-=del;
			if(V[x]==0) T[i].pop_back();
		}
	}
	
	int cnt=(sum[0]+sum[1]+S-1)/S;
	ll ma=0;
	memmove(V2,V,sizeof(V));
	for(int a=0;a<=cnt;a++) {
		memmove(V,V2,sizeof(V));
		ll NA[2]={a*S,(cnt-a)*S};
		ll tmp=0;
		vector<pair<int,int>> T2[2];
		FOR(i,2) {
			T2[i]=T[i];
			while(T2[i].size() && NA[i]) {
				x=T2[i].back().second;
				ll del=min(NA[i],V[x]);
				if(i<1) tmp+=del*A[x];
				else tmp+=del*B[x];
				
				V[x]-=del;
				NA[i]-=del;
				if(V[x]==0) T2[i].pop_back();
			}
			FORR(t,T2[i]) {
				if(i<1) tmp+=V[t.second]*B[t.second];
				else tmp+=V[t.second]*A[t.second];
			}
		}
		ma=max(ma,tmp);
	}
	
	
	cout<<ret+ma<<endl;
	
}

まとめ

しょうもないミスが多いのが残念。