Submission #3429576
Source Code Expand
#include <iostream>
#include <cassert>
#include <climits>
#include <bitset>
#include <stack>
#include <queue>
#include <iomanip>
#include <limits>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
long long int INF = 1e18;
double Pi = 3.1415926535897932384626;
long long int mod = 1000000007;
vector<ll> G[500005];
vector<P> tree[500010];
priority_queue <ll> pql;
priority_queue <P> pqp;
//big priority queue
priority_queue <ll,vector<ll>,greater<ll> > pqls;
priority_queue <P,vector<P>,greater<P> > pqps;
//small priority queue
//top pop
int dx[8]={1,0,-1,0,1,1,-1,-1};
int dy[8]={0,1,0,-1,1,-1,-1,1};
char dir[] = "RULD";
//↓,→,↑,←
#define p(x) cout<<x<<endl;
#define el cout<<endl;
#define pe(x) cout<<x<<" ";
#define ps(x) cout<<fixed<<setprecision(15)<<x<<endl;
#define pu(x) cout<<x;
#define re(i,a,b) for(i=a;i<=b;i++);
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define deba(x) cout<< #x << " = " << x <<endl
ll rui(ll abc,ll bed){
//abcのbed乗を計算する
if(bed==0){return 1;}
else{
ll ced = rui(abc,bed/2);
ced *= ced;
ced %= mod;
if(bed%2==1){ced*=abc; ced%=mod;}
return ced;
}
}
ll gcd(ll number1,ll number2){
if(number1 > number2){
swap(number1,number2);
}
if(number1 == 0 || number1 == number2){
return number2;
}else{
return gcd(number2 % number1,number1);
}
}
ll i,j,k,ii,jj;
ll n,m,num,ans;
ll a,b,c,d,e,g,h,r,bag;
ll wn1,wn2,wn3,wn4;
ll w[5005],v[5005];
ll dp[5][5005];
ll inde[5];
int main(){
cin >> n >> bag;
for(i=0;i<n;i++){
cin >> w[i] >> v[i];
}
for(i=0;i<=3;i++){
inde[i] = 1;
}
for(i=0;i<n;i++){
for(num = 0;num <= 3;num ++){
if(w[i] == w[0] + num){
dp[num][inde[num]++] = v[i];
}
}
}
for(num=0;num<=3;num++){
sort(dp[num] + 1,dp[num] + inde[num] + 1);
reverse(dp[num] + 1,dp[num] + inde[num] + 1);
}
for(i=0;i<=3;i++){
for(j=1;j<=inde[i];j++){
dp[i][j] += dp[i][j-1];
//pe(dp[i][j]);
}
//el;
}
for(int num1=0;num1 <= inde[0];num1 ++){
for(int num2=0;num2 <= inde[1];num2 ++){
for(int num3=0;num3 <= inde[2];num3++){
if((bag-w[0]*num1-w[0]*num2-num2-w[0]*num3-2*num3) < 0)continue;
ll kosuu = (bag-w[0]*num1-w[0]*num2-num2-w[0]*num3-2*num3) / (w[0] + 3);
ll kati = dp[0][num1] + dp[1][num2] + dp[2][num3] + dp[3][kosuu];
ans = max(ans,kati);
}
}
}
p(ans);
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Simple Knapsack |
User |
enjapma |
Language |
C++14 (GCC 5.4.1) |
Score |
400 |
Code Size |
2670 Byte |
Status |
AC |
Exec Time |
9 ms |
Memory |
23680 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
400 / 400 |
Status |
|
|
Set Name |
Test Cases |
Sample |
example0, example1, example2, example3 |
All |
antigreedy0, antigreedy1, antigreedy2, example0, example1, example2, example3, quarter0, quarter1, quarter2, rand0, rand1, rand2, smallw0, smallw1, smallw2 |
Case Name |
Status |
Exec Time |
Memory |
antigreedy0 |
AC |
9 ms |
23680 KB |
antigreedy1 |
AC |
9 ms |
23680 KB |
antigreedy2 |
AC |
9 ms |
23680 KB |
example0 |
AC |
9 ms |
23680 KB |
example1 |
AC |
9 ms |
23680 KB |
example2 |
AC |
9 ms |
23680 KB |
example3 |
AC |
9 ms |
23680 KB |
quarter0 |
AC |
9 ms |
23680 KB |
quarter1 |
AC |
9 ms |
23680 KB |
quarter2 |
AC |
9 ms |
23680 KB |
rand0 |
AC |
9 ms |
23680 KB |
rand1 |
AC |
9 ms |
23680 KB |
rand2 |
AC |
9 ms |
23680 KB |
smallw0 |
AC |
9 ms |
23680 KB |
smallw1 |
AC |
9 ms |
23680 KB |
smallw2 |
AC |
9 ms |
23680 KB |