Submission #918362

#	Time	Username	Problem	Language	Result	Execution time	Memory
918362		Mugiwaraaa	Knapsack (NOI18_knapsack)	C++17	100 / 100	48 ms	6740 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
#define Bankai ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

const int MX_SIZE= 1e3 + 10;
const int oo=1e9 + 1;
const int MOD=1e9+7;

int tc = 1;

void calc( int s , vector<vector<pair<long long , long long>>>&vec , vector<pair<long long , long long>>&used ){

    for( int sum = 1 ; sum <= s ; sum++){

        long long cur = s / sum;
        sort( vec[sum].rbegin() ,  vec[sum].rend() );

        for ( auto &[ val , cnt]: vec[sum] ) {

            long long use = min(cur, cnt);
            cur -= use;
            while (use--)
                used.push_back( {val , sum} );

        }
    }

}

void ROOM() {

     int n , s;cin >> s >> n;

    long long v[n],w[n],k[n];
    vector<vector<pair<long long , long long>>>vec(s + 2 ) ;
    vector<pair<long long , long long>>used;

    for( int i = 0 ; i < n ; i++) {

        cin >> v[i] >> w[i] >> k[i];
        vec[ w[i] ].push_back({v[i] , k[i]});

    }

    long long dp[2][s+2];
    for( int sum = 0 ; sum <= s ; sum++){
        dp[0][sum] = dp[1][sum] = 0;
    }

    calc( s , vec , used );

    int cur = 0;

    for (auto &[ val, sum ]: used) {

        cur ^= 1;

        for (int i = s; i >= sum; i--) {
            dp[cur][i] = max(dp[cur ^ 1 ][i], dp[1 ^ cur][i - sum] + val);
        }

    }


    cout << dp[cur][s];

}
int main() {
    Bankai
    int t = 1;
    //cin>>t;

    while (t--) {
        tc++;

        ROOM();
        if (tc)
            cout << "\n";

    }
    return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 27 / 27