제출 #1128603

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1128603		Born_To_Laugh	Knapsack (NOI18_knapsack)	C++20	100 / 100	317 ms	1892 KiB

knapsack

          /////////////////////////////////////////////////////////////////
         ////////            Born_To_Laugh - Hughie Do            ////////
        /////////////////////////////////////////////////////////////////
// #pragma GCC optimize("unroll-loops")
// #pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MAXN=3e5+5;
const int INF=1e9+7;
/*
    Idea:
*/
void solve(){
    map<int,vector<pair<int,int>>> wei;
    int s, t;
    cin >> s >> t;
    while(t--){
        int v, w, k; 
        cin >> v >> w >> k;
        if(w <= s){
            wei[w].push_back(make_pair(v,k));
        }
    }
    vector<int> dp(s+1, 0);
    for(int i=0; i<=s; ++i){
        if(wei[i].size() == 0)continue;
        sort(wei[i].begin(), wei[i].end(), greater<pair<int,int>>());
        
        int index = 0;
        //xet j so dau tien co can nang i
        for(int j=0;  j*i<=s; ++j){
            if(index >= wei[i].size())break;
            for(int k = s; k>=i; --k){
                dp[k]=max(dp[k], dp[k-i]+wei[i][index].first);
            }
            wei[i][index].second--;
            if(wei[i][index].second == 0)index++;
        }

    }
    cout << dp[s];
}
int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    solve();
    return 0;
}




















































































/*
    Use for suggestion:
    {
        while
    }
    {
        nullptr
        sync_with_stdio
        false
        return
        to_string
        length
    }
    {
        push_back
        pop_back
        sort
        reverse
        begin
        end
        distance
        assign 
    }
    {
        insert
        erase
        lower_bound
        upper_bound
        binary_search
        
    }
    {
        first   
        second
        swap
    }
    {
        double
        float
        unsigned
    }
    {
        unordered_map
        pair
        vector
        deque
        string
        auto
        cout
    }
*/

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