제출 #1326922

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326922		jump	Knapsack (NOI18_knapsack)	C++20	100 / 100	124 ms	9152 KiB

knapsack

#include <bits/stdc++.h>
#define int long long
int value[100010];
int weight[100010];
int amount[100010];
int dpw[2010];//most cost secured from the weight
std::map<int,int> wv[2010];
signed main(){
    int s,n;
    std::cin >> s >> n;
    for(int i=1;i<=n;i++){
        std::cin >> value[i] >> weight[i] >> amount[i];
        wv[weight[i]][-value[i]]+=amount[i];
    }
    for(int k=1;k<=s;k++){
        int arraysize = (((double)s/k) + 1);
        std::vector<int> checkV;
        for(auto &p:wv[k]){
            for(int i=0;i<p.second;i++){
                checkV.push_back(-p.first);
                if(checkV.size()>arraysize){
                    break;
                }
            }
            if(checkV.size()>arraysize){
                break;
            }
        }
        for(auto vc:checkV){
            for(int i=s;i>=k;i--){
                dpw[i]=std::max(dpw[i-k]+vc,dpw[i]);
            }
        }
    }
    //for(int i=0;i<=s;i++)std::cout << dpw[i] << ' ';
    std::cout << dpw[s];
}

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