Good Bye 2016 : C. New Year and Rating

詰めが甘くて最後にIGMから落ちたのが残念。
http://codeforces.com/contest/750/problem/C

問題

N回Codeforcesのラウンドがあった。
各ラウンドにおいてDiv1/2どちらに参加したかと、参加後のレートの変動が与えられる。
Div1はレート1900以上、Div2は1900未満でないと参加できない。
条件を満たすレート変動のうち最大値を求め、最終的なレートを応えよ。

解法

全部Div1参加の場合、レートは無限に大きくできる。
そうでない場合、初期レートを適当に仮置きして、Div2参加したときの最大レートを求める。
条件を満たす場合、その時に1899であるように初期レートを操作すればよい。

なお、その場合レート1900未満でDiv1に参加している可能性があるので最後に再度チェックをすること。

int N;
ll sum[202020];
int D[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x>>D[i];
		sum[i+1]=sum[i]+x;
	}
	ll mi0=1<<30,ma1=-1<<30;
	FOR(i,N) {
		if(D[i]==1) mi0=min(mi0,sum[i]);
		if(D[i]==2) ma1=max(ma1,sum[i]);
	}
	if(mi0<=ma1) return _P("Impossible\n");
	if(ma1==-1<<30) return _P("Infinity\n");
	ll dif;
	FOR(i,N) if(D[i]==2 && ma1==sum[i]) dif=1899-ma1;
	cout<<dif+sum[N]<<endl;
	
	
}

まとめ

Codeforces準拠ならレート変動は±200位でもいいのにね。