Submission #3924457


Source Code Expand

Copy
#include<algorithm>
#include<complex>
#include<ctype.h>
#include<iomanip>
#include<iostream>
#include<map>
#include<math.h>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<stdio.h>
#include<string>
#include<string>
#include<vector>

using namespace std;
typedef long long ll;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("Yes")
#define p_no() p("No")

const ll mod = 1e9 + 7;
const ll inf = 1e18;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N, W;
    cin >> N >> W;

    vector<ll> V0;
    vector<ll> V1;
    vector<ll> V2;
    vector<ll> V3;

    ll w1 = -1;
    FOR(i, 0, N){
        ll w, v;
        cin >> w >> v;
        
        if(w1==-1){
            w1 = w;
        }

        ll diff = w - w1;
        switch(diff){
            case 0:
                V0.push_back(v);
                break;
            case 1:
                V1.push_back(v);
                break;
            case 2:
                V2.push_back(v);
                break;
            case 3:
                V3.push_back(v);
                break;
        }
    }

    sort(ALL(V0), greater<ll>());
    sort(ALL(V1), greater<ll>());
    sort(ALL(V2), greater<ll>());
    sort(ALL(V3), greater<ll>());

    ll n0 = V0.size();
    ll n1 = V1.size();
    ll n2 = V2.size();
    ll n3 = V3.size();

    // 価値の累積和
    ll Ac0[n0];
    ll Ac1[n1];
    ll Ac2[n2];
    ll Ac3[n3];

    if(n0>0) Ac0[0] = V0[0];
    FOR(i, 1, n0){
        Ac0[i] = Ac0[i-1] + V0[i];
    }

    if(n1>0) Ac1[0] = V1[0];
    FOR(i, 1, n1){
        Ac1[i] = Ac1[i-1] + V1[i];
    }

    if(n2>0) Ac2[0] = V2[0];
    FOR(i, 1, n2){
        Ac2[i] = Ac2[i-1] + V2[i];
    }

    if(n3>0) Ac3[0] = V3[0];
    FOR(i, 1, n3){
        Ac3[i] = Ac3[i-1] + V3[i];
    }

    ll value_max = 0;
    FOR(i, 0, n0+1){
        FOR(j, 0, n1+1){
            FOR(k, 0, n2+1){
                FOR(l, 0, n3+1){

                    ll value = 0;
                    ll weight = 0;

                    if(i>0){
                        value += Ac0[i-1];
                        weight += i * w1;
                    }
                    if(j>0){
                        value += Ac1[j-1];
                        weight += j * (w1+1);
                    }
                    if(k>0){
                        value += Ac2[k-1];
                        weight += k * (w1+2);
                    }
                    if(l>0){
                        value += Ac3[l-1];
                        weight += l * (w1+3);
                    }
                    
                    if(weight <= W){
                        value_max = max(value_max, value);
                    }
                }
            }
        }
    }

    p(value_max);
    
    return 0;
}

Submission Info

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

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
× 4
× 16
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 1 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 3 ms 256 KB
quarter2 3 ms 256 KB
rand0 1 ms 256 KB
rand1 1 ms 256 KB
rand2 1 ms 256 KB
smallw0 2 ms 256 KB
smallw1 3 ms 256 KB
smallw2 2 ms 256 KB