Submission #1288421

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288421		pecorine	Knapsack (NOI18_knapsack)	C++20	100 / 100	55 ms	17612 KiB

knapsack

#include <bits/stdc++.h> // clang-format off
#define princess_connect(file,extention) if(fopen(file "." extention, "r")) freopen(file "." extention, "r", stdin)
#define yabai_desune ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define __Pecorine__ signed main()
#define For(i, l, r) for (int i = l; i <= r; i++)
#define Fod(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
#define pb push_back
#define sz(yuuki) (int)yuuki.size()
#define bit(x,i) (x >> i) & 1
#define endl "\n"
using namespace std;/* //
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠙⠻⠟⠛⠻⢿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠂⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢻⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣦⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢻⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡆⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⣿
⣿⣿⣿⡟⠿⠿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⡀⠀⠀⠀⠀⠀⠀⠀⠀⢠⣀⠀⢸⣿
⣿⡄⠀⠀⠀⠀⠀⠻⠿⣿⣿⣿⣿⣿⡷⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⣼⣿⣿⣿
⣿⣷⡀⠀⠀⠀⠀⠀⠀⠀⠈⠉⠛⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⣿
⣿⣿⣿⣷⣶⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⣿⣿⣿
⣿⣿⣿⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠋⣉⣽
⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢿⣿⣿
⣿⣿⣿⣿⡏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢿⣿
*/ // clang-format on
const int inf = 2e9;
const int mxn = 1e5 + 7;
const int mod = 1e9 + 7;

int s, n;

__Pecorine__ {
    yabai_desune;
    princess_connect("yabai", "desune");
    cin >> s >> n;
    map<int, vector<pair<int, int>>> type;
    For(i, 1, n) {
        int v, w, k; cin >> v >> w >> k;
        type[w].pb({v, k});
    }
    
    vector<vector<int>> f(sz(type) +  1, vector<int>(2007));

    int id = 1;
    for(auto &[w, items] : type) {
        sort(items.begin(), items.end(), greater<pair<int ,int>>());
        For(i, 0, s) {
            f[id][i] = f[id - 1][i];

            int copy = 0;
            int at = 0;
            int cnt = items[at].second;
            int sum = 0;
            while(i - (copy + 1) * w >= 0 && at < sz(items)) {
                copy++;
                sum += items[at].first;
                f[id][i] = max(f[id][i], f[id - 1][i - copy * w] + sum);
                cnt--;
                if(cnt == 0) {
                    at++;
                    cnt = items[at].second;
                }
            }
        }
        id++;
    }
    cout << f.back()[s];
    // id = 1;
    // for(auto &[w, items] : type) {
    //     For(i, 1, s) {
    //         cout << f[id][i] << " ";
    //     }
    //     cout << endl;
    //     id++;
    // }
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:2:84: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    2 | #define princess_connect(file,extention) if(fopen(file "." extention, "r")) freopen(file "." extention, "r", stdin)
      |                                                                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:39:5: note: in expansion of macro 'princess_connect'
   39 |     princess_connect("yabai", "desune");
      |     ^~~~~~~~~~~~~~~~

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