JOI 2009 春合宿 day2-3 「Contest」

貪欲法でおk。
まず自分（問い合わせのあった国）が取りうる最大の得点Xを求め、
あとは適当に、Xを出来る限り超えないように当てはめていく。

#include<cstdio>
#include<algorithm>
#include<vector>
#define rep(i,n) for(int i = 0; i < n; i++)
#define rrep(i,n) for(int i = 1; i <= n; i++)
#define pb push_back
using namespace std;

vector<int> sc[3001], co[3];

int main(){
	int n, c, s, a, m, x, y, z, ans = 1;
	
	scanf("%d%d",&n,&c);
	
	rep(i,n*2){
		scanf("%d%d",&s,&a);
		sc[a].pb(s);
	}
	
	sort(sc[0].begin(), sc[0].end());
	m = sc[0].size()-1; 
	for(int i = sc[c].size(); i < 2; i++){ sc[c].pb(sc[0][m]); m--;}
	x = sc[c][0] + sc[c][1];
	
	rrep(i,n){
		co[sc[i].size()].pb(i);
	}
	
	rep(i,co[2].size()) if(sc[co[2][i]][0] + sc[co[2][i]][1] > x) ans++;
	
	rep(i,co[1].size()){
		y = x - sc[co[1][i]][0];
		z = m;
		for(int j = 0; j <= m; j++){
			if(sc[0][j] > y) break;
			if(sc[0][j] != -1) z = j;
		}
		
		if(z == m){
			if(sc[0][m] > y) ans++;
			while(m>0){
				m--;
				if(sc[0][m] != -1) break;
			}
		} else {
			sc[0][z] = -1;
		}
	}
	
	
	rep(i,m){
		if(sc[0][i] != -1){
			y = x - sc[0][i];
			z = m;
			for(int j = i+1; j <= m; j++){
				if(sc[0][j] > y) break;
				if(sc[0][j] != -1) z = j;
			}
			
			if(z == m){
				if(sc[0][m] > y) ans++;
				while(m>0){
					m--;
					if(sc[0][m] != -1) break;
				}
			} else {
				sc[0][z] = -1;
			}
		}
	}
	
	printf("%d\n",ans);
	
	return 0;
}