Submission #3234827

---

Source Code Expand

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main() {
	int n;cin>>n;
	long long W;cin>>W;
	vector<long long> w(n),v(n);
	vector<vector<long long>> a(4,vector<long long>(0));
	for(int i=0;i<n;i++){
		cin>>w[i]>>v[i];
		a[w[i]-w[0]].push_back(v[i]);
	}
	for(int i=0;i<4;i++){
		sort(a[i].begin(),a[i].end(),greater<long long>());
		for(int j=1;j<a[i].size();j++){
			a[i][j]+=a[i][j-1];
		}
	}
	long long ans=0;
	for(int i=0;i<=a[0].size();i++){
		for(int j=0;j<=a[1].size();j++){
			for(int k=0;k<=a[2].size();k++){
				for(int l=0;l<=a[3].size();l++){
					int b[4];
					b[0]=i;
					b[1]=j;
					b[2]=k;
//					int l=n-i-j-k;
					b[3]=l;
//					if(l<0)continue;
//					if(l>a[3].size())continue;
					long long wsum=0;
					long long vsum=0;
					for(int m=0;m<4;m++){
						wsum+=b[m]*(w[0]+m);
						if(b[m]){
						vsum+=a[m][b[m]-1];
						}
					}
//					cout<<i<<' '<<j<<' '<<k<<' '<<wsum<<' '<<vsum<<endl;
					if(wsum<=W){
						if(ans<vsum)ans=vsum;
					}
				}

			}
		}
	}
//	for(int i=0;i<4;i++){
//		for(int j=0;j<a[i].size();j++){
//			cout<<a[i][j]<<' ';
//		}
//		cout<<endl;
//	}
	cout<<ans<<endl;

	return 0;
}

Submission Info

Judge Result