제출 #1103031

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1103031		SoMotThanhXuan	Knapsack (NOI18_knapsack)	C++17	100 / 100	39 ms	3836 KiB

knapsack

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
using namespace std;
const int maxS = 2e3 + 1;
int N, S;
int  f[maxS];
vector<pair<int, int>> item[maxS];
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> S >> N;
    for(int i = 1, v, w, k; i <= N; ++i){
        cin >> v >> w >> k;
        item[w].push_back({v, k});
    }
    for(int w = 1; w <= S; ++w)sort(item[w].begin(), item[w].end(), greater<pair<int, int>>());
//    for(int w = 1; w <= S; ++w){
//        if(item[w].size()){
//            cout << w << "\n";
//            for(auto[v, k] : item[w])cout << v << ' ' << k << "\n";
//
//        }
//    }
    for(int s = 1; s <= S; ++s){
        for(int j = S; j >= 1; --j){
            int W = 0;
            int V = 0;
            for(auto [v, k] : item[s]){
                for(int cnt = 1; cnt <= k; ++cnt){
                    W += s;
                    V += v;
                    if(W <= j) f[j] = max(f[j], f[j - W] + V);
                    else break;
                }
                if(W <= j)continue;
                else break;
            }
        }
    }
//    for(int s = 0; s <= S; ++s){
//        cout << f[s] << ' ';
//    }cout << '\n';
    cout << *max_element(f, f + S + 1);
    return 0;
}

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