Submission #3233007
Source Code Expand
#include <iostream>
#include <vector>
#include <math.h>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <string>
#include <cstring>
#include <regex>
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pl4 = pair<ll,ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vs = vector<string>;
using vvs = vector<vs>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vpii = vector<pii>;
using vvpii = vector<vpii>;
using vpl4 = vector<pl4>;
using vvpl4 = vector<vpl4>;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pob pop_back()
#define sz size()
#define be begin()
#define en end()
#define asn assign
#define emp empty()
#define ft front()
#define bk back()
#define clr clear()
#define ins insert
#define ers erase
#define res resize
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define rFOR(i,a,b) for(int i=(b);i>=(a);i--)
#define REP(i,a) for(int i=0;i<(a);i++)
#define REP1(i,a) for(int i=1;i<=(a);i++)
#define rREP(i,a) for(int i=(a-1);i>=0;i--)
#define rREP1(i,a) for(int i=(a);i>0;i--)
#define SORT(a) sort((a).be,(a).en)
#define rSORT(a) sort((a).rbegin(),(a).rend())
#define UNIQUE(a) (a).erase(unique((a).be,(a).en),(a).en)
#define PREVP(a) prev_permutation((a).be,(a).en)
#define NEXTP(a) next_permutation((a).be,(a).en)
#define BINS(a,b) binary_search((a).be,(a).en,(b))
#define LOWB(a,b) (lower_bound((a).be,(a).en,(b))-(a).be)
#define UPB(a,b) (upper_bound((a).be,(a).en,(b))-(a).be)
#define CNT(a,b) count((a).be,(a).en,b)
#define SUM(a) accumulate((a).be,(a).en,0)
#define REV(a) reverse((a).be,(a).en)
#define REGS(a,b) regex_search((a),regex(b))
#define REGM(a,b) regex_match((a),regex(b))
#define yn(a) cout <<((a)?"yes":"no")<<endl;
#define Yn(a) cout <<((a)?"Yes":"No")<<endl;
#define YN(a) cout <<((a)?"YES":"NO")<<endl;
#define say(a) cout <<(a);
#define sal(a) cout <<(a)<<endl;
#define sak cout <<endl;
#define dbg(a) cout <<(#a)<<": "<<(a)<<endl;
#define a2l(a) ((ll)(a-97))
#define A2l(a) ((ll)(a-65))
#define l2a(a) ((char)(a+97))
#define l2A(a) ((char)(a+65))
#define DigN2(a) ((llabs(a)==0)?(1):((ll)(log2(double(llabs(a))))+1))
#define DigN10(a) ((llabs(a)==0)?(1):((ll)(log10(double(llabs(a))))+1))
#define Dig2(a,b) (((a)>>(b))&1)
#define Dig10(a,b) (ll)(((a)/((ll)(pow(10.0,(double)(b)))))%10)
#define Pow2(a) (1<<(a))
#define llin(a) ll (a);cin >>(a);
#define stin(a) string (a);cin >>(a);
#define rdn(a,b) ((a)/(b))
#define rou(a,b) ((((double(a)/double(b))-((a)/(b)))<0.5)?((a)/(b)):(((a)/(b))+1))
#define rup(a,b) ((((a)%(b))==0)?((a)/(b)):(((a)/(b))+1))
#define min(a,b) ((a<b)?(a):(b))
#define max(a,b) ((a>b)?(a):(b))
#define int ll
const ll MOD = 1e9+7;
const string alp = "abcdefghijklmnopqrstuvwxyz";
const string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
ll gcd(ll a, ll b){if(b==0)return a;return gcd(b,a%b);}
ll lcm(ll a, ll b){return a/gcd(a,b)*b;}
ll sgn(ll n){
if(n==0) return 0;
else return n/abs(n);
}
ll salv(vll v){
say("{");
FOR(i,0,v.sz-1){
say(v[i]);
if(i!=v.sz-1) say(",");
}
sal("}")
}
ll DigS10(ll n){
ll m=0;
FOR(i,0,DigN10(n)-1){
m+=(ll)((llabs(n)%(ll)(pow(10.0,(double)(i+1))))/(ll)(pow(10.0,(double)i)));
}
return m;
}
ll isP(ll n){
if(n<=1) return 0;
FOR(i,2,(ll)sqrt(n)){
if(n%i==0) return 0;
}
return 1;
}
vll FactM(1,1);
vll FactMI(1,1);
ll PowM(ll a,ll b){
ll ans=1,x=(a%MOD);
FOR(i,0,DigN2(b)-1){
if(Dig2(b,i)==1) ans=(ans*x)%MOD;
if(i!=(DigN2(b)-1)) x=(x*x)%MOD;
}
return ans;
}
void CFactM(ll n){
FOR(i,FactM.sz,n){
FactM.pb((FactM[i-1]*(i%MOD))%MOD);
}
return;
}
void CFactMI(ll n){
CFactM(n);
if(FactMI.sz<(n+1)) FactMI.res(n+1,-1);
if(FactMI[n]==-1) FactMI[n]=PowM(FactM[n],MOD-2);
rFOR(i,1,n-1){
if(FactMI[i]!=-1) break;
FactMI[i]=((FactMI[i+1]*((i+1)%MOD))%MOD);
}
return;
}
ll CombM(ll n,ll k){
if((n<0)||(k<0)) return 0;
if(n<k) return 0;
if(n+1>FactMI.sz) CFactMI(n);
return ((((FactMI[k]*FactMI[n-k])%MOD)*FactM[n])%MOD);
}
signed main() {
ll n,w,ww,vv,dw,vt0,vt1,vt2,vt3,r=0,t;
vll v0,v1,v2,v3;
cin >> n >> w;
REP(i,n){
cin >> ww >> vv;
if(!i){
dw=ww;
v0.pb(vv);
} else {
if(dw==ww){
v0.pb(vv);
} else if (dw+1==ww) {
v1.pb(vv);
} else if (dw+2==ww) {
v2.pb(vv);
} else {
v3.pb(vv);
}
}
}
rSORT(v0);
rSORT(v1);
rSORT(v2);
rSORT(v3);
vt0=0;
for(int i=0;i*dw<=w;i++){
vt1=0;
for(int j=0;i*dw+j*(dw+1)<=w;j++){
vt2=0;
for(int k=0;i*dw+j*(dw+1)+k*(dw+2)<=w;k++){
vt3=0;
for(int l=0;i*dw+j*(dw+1)+k*(dw+2)+l*(dw+3)<=w;l++){
t=vt0+vt1+vt2+vt3;
if(r<t)r=t;
if(v3.size()>l){
vt3+=v3[l];
} else {
l=100;
}
}
if(v2.size()>k){
vt2+=v2[k];
} else {
k=100;
}
}
if(v1.size()>j){
vt1+=v1[j];
} else {
j=100;
}
}
if(v0.size()>i){
vt0+=v0[i];
} else {
i=100;
}
}
cout << r;
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Simple Knapsack |
User |
V_Melville |
Language |
C++14 (GCC 5.4.1) |
Score |
400 |
Code Size |
5359 Byte |
Status |
AC |
Exec Time |
1 ms |
Memory |
256 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 |
1 ms |
256 KB |
antigreedy1 |
AC |
1 ms |
256 KB |
antigreedy2 |
AC |
1 ms |
256 KB |
example0 |
AC |
1 ms |
256 KB |
example1 |
AC |
1 ms |
256 KB |
example2 |
AC |
1 ms |
256 KB |
example3 |
AC |
1 ms |
256 KB |
quarter0 |
AC |
1 ms |
256 KB |
quarter1 |
AC |
1 ms |
256 KB |
quarter2 |
AC |
1 ms |
256 KB |
rand0 |
AC |
1 ms |
256 KB |
rand1 |
AC |
1 ms |
256 KB |
rand2 |
AC |
1 ms |
256 KB |
smallw0 |
AC |
1 ms |
256 KB |
smallw1 |
AC |
1 ms |
256 KB |
smallw2 |
AC |
1 ms |
256 KB |