貪欲法でお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; }