Codeforces #255 Div1 B. DZY Loves Modification

割とすぐすんなり解法が思いついたのに、無駄にオーバーフローして時間とWAで損した…。
http://codeforces.com/contest/446/problem/B

問題

N*M要素の行列及び整数K,Pが与えられる。
この行列に対し、以下の処理をK回行う。

• 1つ行を選択し、その行の各要素をP減らす。その際、減らす前の行の値の総和分ポイントが得られる。
• 1つ列を選択し、その列の各要素をP減らす。その際、減らす前の列の値の総和分ポイントが得られる。

最大で得られるポイントはいくらか。

解法

行の選択を何度か行うなら、当然行の総和が多い順に選択するのが賢い。列も同様。
よって、まずは行だけおよび列だけ0～K回処理を行った時得られるポイントを事前に計算しておく。
これはpriority_queueを使い行・列の総和を管理することでO(K*(logN+logM))で行える。

問題は行と列が混在する場合である。
先に行を選択すると、その行の値が各列Pずつ減るので、次にどこの列を選らんでもP減少の影響を受ける。
列を先に選択した場合も同様。

よって、行と列の選択順は関係ないことがわかる。
そこで、行をx回、列をK-x回選択する場合を総当たりし、（行選択によるポイント増分＋列選択によるポイント増分＋行・列選択によるポイント減少分）の最大値を求めればよい。

ll H,W,K,P;
int A[1001][1001];
priority_queue<ll> RR,CC;
ll RV[1001];
ll CV[1001];
ll SR,SC;

ll RS[1000001];
ll CS[1000001];


void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>H>>W>>K>>P;
	FOR(y,H) FOR(x,W) cin>>A[y][x];
	FOR(y,H) FOR(x,W) RV[y]+=A[y][x],CV[x]+=A[y][x];
	FOR(y,H) RR.push(RV[y]);
	FOR(x,W) CC.push(CV[x]);
	
	FOR(i,K) {
		ll mr=RR.top();
		ll mc=CC.top();
		RS[i+1]=RS[i]+mr;
		CS[i+1]=CS[i]+mc;
		RR.pop();
		RR.push(mr-W*P);
		CC.pop();
		CC.push(mc-H*P);
	}
	
	ll ma=-1LL<<60;
	FOR(i,K+1) {
		ma=max(ma,RS[i]+CS[K-i]-x*(LL)i*(int)P);
	}
	
	cout << ma << endl;
}

まとめ

オーバーフローしなければレート維持できたのにな。