제출 #1322960

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1322960		aryan	Knapsack (NOI18_knapsack)	C++20	12 / 100	195 ms	327680 KiB

knapsack

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

using i64 = long long;


int main(){
        
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int s,n;
    cin >> s >> n;
    vector<vector<pair<int,int>>> hs(s + 1);
    for(int i = 0;i < n;i++){
        int v,w,k;
        cin >> v >> w >> k;
        hs[w].push_back({v,k});
    } 
    vector<vector<int>> tot(s + 1);
    for(int i = 1;i <= s;i++){
        sort(hs[i].begin(),hs[i].end(),greater<pair<int,int>>());
        vector<pair<int,int>> vec;
        pair<int,int> p = {-1,-1};
        for(int j = 0;j < (int)hs[i].size();j++){
            if(p.first != hs[i][j].first){
                if(p.first != -1){
                    vec.push_back(p);
                }
                p = hs[i][j];
            }else{
                p.second += hs[i][j].second;
            }
        }
        if(p.first != -1) vec.push_back(p);
        hs[i] = vec;
        int num = 0;
        for(pair<int,int> p : hs[i]){
            if(num == s / i) break;
            for(int j = 0;j < p.second;j++){
                tot[i].push_back(p.first);
                num ++;
                if(num == s / i) break;
            }
        }
        while(tot[i].size() < s / i) tot[i].push_back(0);
    }

    // for(int i = 1;i <= s;i++){
    //     cout << i << " : \n";
    //     for(pair<int,int> &e : hs[i]){
    //         cout << e.first << " " << e.second << '\n';
    //     }
    // }

    // vector<vector<i64>> dp(s + 2,vector<i64>(s + 2));
    // if currently at (i,j) -> ith weight,s space left

    vector<vector<vector<i64>>> dp(s + 2,vector<vector<i64>>(s + 1));
    for(int i = 1;i <= s + 1;i++){
        for(int j = 0;j <= s;j++){
            dp[i][j] = vector<i64>((s / i) + 5);
        }
    }

    for(int i = s;i >= 1;i--){
      for(int k = (s / i);k >= 0;k--){        
        for(int j = i;j <= s;j++){
            // take
            if(k < (int) tot[i].size()) dp[i][j][k] = dp[i][j - i][k + 1] + tot[i][k];
            // not take
            dp[i][j][k] = max(dp[i][j][k],dp[i + 1][j][0]);
        }
    }
}

    cout << dp[1][s][0] << '\n';
    
    return 0;
}

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