2009 Contest

不思議なGreedyがたくさん必要です。
まあ、問い合わせの国以外でなるべく沢山詰め込むときには、努力して詰め込もうとする範囲を上からおさえてやります。するとうまーい具合に通ります。本当こういうの怖い。

#include<stdio.h>
#include<algorithm>
using namespace std;
int c[6000],d[6000],e[3000],f[3000],g[6000],h[3000];
bool use[6000];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	b--;
	for(int i=0;i<a*2;i++){
		scanf("%d%d",c+i,d+i);
	}
	int now=0;
	for(int i=0;i<a*2;i++){
		if(d[i]){
			f[d[i]-1]++;
			e[d[i]-1]+=c[i];
		}else{
			g[now++]=c[i];
		}
	}
	std::sort(g,g+now);
	while(f[b]<2){
		now--;
		f[b]++;
		e[b]+=g[now];
	}
	int t=0;
	int u=0;
	for(int i=0;i<a;i++){
		if(f[i]==1){
			h[t++]=e[i];
		}else if(f[i]==0){
			u++;
		}
	}
	std::sort(h,h+t);
	int ret=0;
	for(int i=0;i<=now;i++){
		int val=0;
		int at=now-1;
		int lim=(now-t)/2;
		for(int j=0;j<now;j++)use[j]=false;
		for(int j=0;j<i;j++){
			if(!use[j]&&lim){
				while(at>j&&(g[at]+g[j]>e[b]||use[at])){
					at--;
				}
				if(at>j){
					use[at]=use[j]=true;
					at--;
					val++;
					lim--;
				}
			}
		}
		at=now-1;
	//	printf("%d\n",val);
		for(int j=0;j<t;j++){
			if(i!=now&&h[j]>=g[i])continue;
			while(at>=0&&(g[at]+h[j]>e[b]||use[at])){
				at--;
			}
			if(at>=0){
				use[at]=true;
				at--;
				val++;
			}
		}
		ret=max(ret,val);
	}
	//printf("%d\n",ret);
	for(int i=0;i<=t;i++){
		int val=0;
		int at=now-1;
		int lim=(now-t)/2;
		for(int j=0;j<now;j++)use[j]=false;
		for(int j=0;j<i;j++){
			while(at>=0&&(g[at]+h[j]>e[b]||use[at])){
				at--;
			}
			if(at>=0){
				use[at]=true;
				at--;
				val++;
			}
		}
		at=now-1;
		for(int j=0;j<now;j++){
			if(i!=t&&g[j]>=h[i])continue;
			if(!use[j]&&lim){
				while(at>j&&(g[at]+g[j]>e[b]||use[at])){
					at--;
				}
				if(at>j){
					use[at]=use[j]=true;
					at--;
					val++;
					lim--;
				}
			}
		}
		ret=max(ret,val);
	}
	for(int i=0;i<a;i++){
		if(f[i]==2&&e[i]<=e[b])ret++;
	}
	printf("%d\n",a-ret+1);
}