Codeforces #288 Div2 C. Anya and Ghosts

CF288に参加。
ABCまでサクサク解いたものの、Eで手間取り、Dは解けず。
http://codeforces.com/contest/508/problem/C

問題

時間tだけ点灯する蝋燭がある。
時間１当たり１個だけ新たな蝋燭をつけることができる。

ここで、m匹の幽霊が時刻W[i]に現れる。
幽霊をやり過ごすには、蝋燭をr本以上ついた状態にする必要がある。

全ての幽霊をやり過ごすのに必要な最小蝋燭本数を求めよ。

解法

各W[i]について、(W[i]-t+1)～(W[i])のうち時刻の大きい順に、蝋燭がr本に達するまで蝋燭をつければよい。

int M,T,R;
int W[400];
int on[800];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>M>>T>>R;
	FOR(i,M) {
		cin>>W[i];
		y=R;
		for(x=W[i];x>W[i]-T;x--) if(on[x+400]) y--;
		if(y<=0) continue;
		for(x=W[i];x>W[i]-T && y>0;x--) if(on[x+400]==0) on[x+400]=1, y--;
		if(y) return _P("-1\n");
	}
	_P("%d\n",count(on,on+800,1));
}

まとめ

Div2とはいえCにしてはヒネリがないかも。