제출 #1290433

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290433		hssaan_arif	Knapsack (NOI18_knapsack)	C++20	73 / 100	280 ms	327680 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;

#define endl "\n"
#define pb push_back
#define int long long
#define fi first
#define se second

const int n = 1e6 + 5, m = 2e3 + 5 ,  M = 1e9 + 7, LG = 20;

int N , S , V[n] , W[n] , K[n] , Dp[2][m];

vector<pair<int,int>> Wi[m] , A(1);

void solve(){
    cin >> S >> N;
    for (int i=1 ; i<=N ; i++){
        cin >> V[i] >> W[i] >> K[i];
        Wi[W[i]].pb({V[i],K[i]});
    }
    for (int i=1 ; i<=S ; i++){
        sort(Wi[i].begin() , Wi[i].end());
        int mx = (S/i);
        while(Wi[i].size()){
            auto p = Wi[i].back();
            if (mx - p.se >= 0){
                while(p.se--){
                    A.pb({p.fi,i});
                }
                Wi[i].pop_back();
                mx -= p.se;
            }else{
                while(mx--){
                    A.pb({p.fi,i});
                }
                break;
            }
        }

    }
    N = A.size()-1;
    for (int i=0 ; i<=N ; i++){
        for (int j=0 ; j<=S ; j++){
            Dp[i%2][j] = -1e18;
            
        }
    }
    for (int i=0 ; i<=N ; i++){
        Dp[i%2][0] = 0;
    }
    for (int i=1 ; i<=N ; i++){
        for (int j=1 ; j<=S ; j++){
            Dp[i%2][j] = Dp[(i-1)%2][j];
            if(j>=A[i].se) Dp[i%2][j] = max(Dp[i%2][j] , Dp[(i-1)%2][j - A[i].se] + A[i].fi);
            
            
        }
    }
    int ans = 0;
    for (int i=1 ; i<=S ; i++){
        ans = max(ans , Dp[N%2][i]);
    }
    cout << ans << endl;
}

signed main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int ts = 1;
    // cin >> ts;
    while(ts--){
        solve();
    }
}

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