Submission #1675923


Source Code Expand

Copy
#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define RREP(i,a,b) for(int i=(a);i>=(b);i--)
typedef long long ll; typedef long double ld;
using namespace std;
const int INF=1e9, MOD=1e9+7;
int n,u,a,b;
ll tmp;
vector<int> vec[4];

int main(){
	cin >> n >> u;
	REP(i,0,n){
		if(!i) cin >> tmp >> b,vec[0].push_back(b);
		else cin >> a >> b,vec[a-tmp].push_back(b);
	}
	
	ll sum[4][110]={};
	REP(i,0,4) sort(vec[i].rbegin(),vec[i].rend());
	REP(i,0,4) REP(j,0,vec[i].size()) sum[i][j+1]=sum[i][j]+vec[i][j];	
	
	ll ma=0;
	REP(i,0,vec[0].size()+1){
		REP(j,0,vec[1].size()+1){
			REP(k,0,vec[2].size()+1){
				REP(l,0,vec[3].size()+1){
					ll pos=i*tmp+j*(tmp+1)+k*(tmp+2)+l*(tmp+3);
					ll v=sum[0][i]+sum[1][j]+sum[2][k]+sum[3][l];
					if(pos<=u) ma=max(ma,v);
				}
			}
		}
	}
	
	cout << ma << endl;
	return 0;
}

Submission Info

Submission Time
Task D - Simple Knapsack
User ecasdqina
Language C++14 (GCC 5.4.1)
Score 400
Code Size 877 Byte
Status
Exec Time 2 ms
Memory 256 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 example0, example1, example2, example3
All 400 / 400 antigreedy0, antigreedy1, antigreedy2, example0, example1, example2, example3, quarter0, quarter1, quarter2, rand0, rand1, rand2, smallw0, smallw1, smallw2
Case Name Status Exec Time Memory
antigreedy0 2 ms 256 KB
antigreedy1 1 ms 256 KB
antigreedy2 1 ms 256 KB
example0 1 ms 256 KB
example1 1 ms 256 KB
example2 1 ms 256 KB
example3 1 ms 256 KB
quarter0 2 ms 256 KB
quarter1 2 ms 256 KB
quarter2 2 ms 256 KB
rand0 1 ms 256 KB
rand1 1 ms 256 KB
rand2 1 ms 256 KB
smallw0 2 ms 256 KB
smallw1 2 ms 256 KB
smallw2 2 ms 256 KB