제출 #1323229

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1323229		darsh_sodani007	Knapsack (NOI18_knapsack)	C++20	100 / 100	424 ms	8084 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define pb push_back
typedef long long llo;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int s,n;
    cin >> s >> n;
    map<int,vector<pair<int,int>>> w;
    for (int i=0;i<n;i++){
        int v,ww;
        llo k;
        cin >> v >> ww >> k;
        k=min(k,(llo)s/ww);
        w[ww].pb({v,k});
    }
    vector<pair<int,pair<int,int>>> v;
    for (auto it:w){
        sort(it.second.rbegin(),it.second.rend());
        int y=0;
        for (int i=0;i<it.second.size();i++){
            if (y+it.second[i].second<=s){
                v.pb({it.first,{it.second[i].first,it.second[i].second}});
                y+=it.second[i].second;
            }
            else{
                v.pb({it.first,{it.second[i].first,s-y}});
                break;
            }
        }
    }
    vector<pair<int,int>> l;
    for (int i=0;i<v.size();i++){
        for (int j=0;j<v[i].second.second;j++){
            l.pb({v[i].second.first,v[i].first});
        }
    }
    vector<llo> dp(s+1,0);
    for (int i=0;i<l.size();i++){
        for (int j=s;j>=l[i].second;j--){
            dp[j]=max(dp[j],dp[j-l[i].second]+l[i].first);
        }
    }
    cout<<dp[s]<<endl;
}

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