제출 #1241647

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1241647		tritranminh2808	Knapsack (NOI18_knapsack)	C++20	100 / 100	36 ms	5448 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define int long long
bool cmp(pair <int,int> a, pair <int, int > b){
    return a.first > b.first;
}
vector< pair< int , int>> g[100005];
int dp[100005];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int s,n;cin>>s>>n;
    
    for(int i=0;i<n;i++){
        int v,k,w;
        cin >> v >> w >> k;
        if(w<=s)g[w].push_back({v,k});
    }
    vector<pair<int,int>> a;
    for(int w=1;w<=s;w++){
        auto& dsach = g[w]; if(dsach.empty()) continue;
        sort(dsach.begin(), dsach.end(), cmp);
        int sech = s/w, lay = 0;
        for(auto p : dsach){ 
            int v = p.first, k = p.second;
            int c = min(k, sech - lay);
            for(int i = 0; i < c; i++) a.push_back({w, v});
            lay += c;
            if(lay >= sech) break;
        }
    }
    for(auto i:a){ 
        int w = i.first; int v = i.second;
        for(int j = s; j >= w; j--) dp[j] = max(dp[j], dp[j-w] + v);
    }
    cout<<dp[s];
}

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