Submission #1962301

---

Source Code Expand

#include<stdio.h>
#include<algorithm>
using namespace std;
int w[210];
int v[210];
long long dp[210000];
long long mod=1000000007;
long long inf=mod*mod;
pair<long long,long long> tmp[50000];
long long snuke[51000];
long long petr[51000];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	int wm=0;
	int vm=0;
	for(int i=0;i<a;i++){
		scanf("%d%d",v+i,w+i);
		wm=max(wm,w[i]);
		vm=max(vm,v[i]);
	}
	if(a<=30){
		int L=a/2;
		int R=a-L;
		int sz=(1<<L);
		for(int i=0;i<(1<<L);i++){
			long long V=0;
			long long W=0;
			for(int j=0;j<L;j++){
				if(i&(1<<j)){
					V+=v[j];
					W+=w[j];
				}
			}
			tmp[i]=make_pair(W,V);
		}
		std::sort(tmp,tmp+sz);
		long long cur=0;
		for(int i=0;i<sz;i++){
			cur=max(cur,tmp[i].second);
			snuke[i]=tmp[i].first;
			petr[i]=cur;
		}
		long long ret=0;
		for(int i=0;i<(1<<R);i++){
			long long V=0;
			long long W=0;
			for(int j=0;j<R;j++){
				if(i&(1<<j)){
					V+=v[L+j];
					W+=w[L+j];
				}
			}
			if(W>b)continue;
			int at=upper_bound(snuke,snuke+sz,b-W)-snuke-1;
			ret=max(ret,petr[at]+V);
		}
		printf("%lld\n",ret);
	}else if(a<=200&&wm<=1000){
		b=min(b,200000);
		for(int i=0;i<210000;i++){
			dp[i]=-inf;
		}
		dp[0]=0;
		for(int i=0;i<a;i++){
			for(int j=b-w[i];j>=0;j--){
				dp[j+w[i]]=max(dp[j+w[i]],dp[j]+v[i]);
			}
		}
		long long ret=0;
		for(int i=0;i<=b;i++)ret=max(ret,dp[i]);
		printf("%lld\n",ret);
	}else if(a<=200&&vm<=1000){
		for(int i=0;i<210000;i++){
			dp[i]=inf;
		}
		dp[0]=0;
		for(int i=0;i<a;i++){
			for(int j=200000-v[i];j>=0;j--){
				dp[j+v[i]]=min(dp[j+v[i]],dp[j]+w[i]);
			}
		}
		int ret=0;
		for(int i=0;i<=200000;i++){
			if(dp[i]<=b)ret=i;
		}
		printf("%d\n",ret);
	}else return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:14:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&a,&b);
                     ^
./Main.cpp:18:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",v+i,w+i);
                        ^

Judge Result