Codeforces #519 E. Train Hard, Win Easy

また微妙な出来だった…
http://codeforces.com/contest/1043/problem/E

問題

N人の人と２問の問題がある。
各人にとって、両問題を解いて得られるスコアはそれぞれA[i],B[i]である。

２人でペアを組み２人で２問を解くことを考える。
その際は、１人１問ずつ担当し、スコアの総和が最小となるように担当する。

また、２人組を組みたくないペアがM個指定される。
各人に対し、可能な全ペアを組んだ時のスコアの総和を求めよ。

解法

M個の組みたくないペアの分は後で引くことにする。
A[i]-B[i]で人をソートすると、この値が小さい人ほどBを担当する方が良い、ということを用いて各人のA,Bの担当回数を求めることができる。
また、相手の担当分のスコアも累積和の要領で求めることができる。

int N,M;
ll X[303030],Y[303030];
vector<int> NG[303030];
ll tot[303030];
pair<ll,int> P[303030];


int hoge(int a,int b) {
	return min(X[a]+Y[b],X[b]+Y[a]);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d",&N,&M);
	FOR(i,N) {
		scanf("%d%d",&x,&y);
		X[i]=x;
		Y[i]=y;
		P[i]={X[i]-Y[i],i};
	}
	
	sort(P,P+N);
	ll S=0;
	FOR(i,N) {
		x=P[i].second;
		tot[x]+=i*Y[x]+S;
		S+=X[x];
	}
	reverse(P,P+N);
	S=0;
	FOR(i,N) {
		x=P[i].second;
		tot[x]+=i*X[x]+S;
		S+=Y[x];
	}
	
	
	FOR(i,M) {
		scanf("%d%d",&x,&y);
		x--,y--;
		tot[x]-=hoge(x,y);
		tot[y]-=hoge(x,y);
	}
	FOR(i,N) cout<<tot[i]<<" ";
	cout<<endl;
	
}

解法

まぁここまではすんなり。