Submission #1355225

#	Time	Username	Problem	Language	Result	Execution time	Memory
1355225		merlin1205	Knapsack (NOI18_knapsack)	C++20	100 / 100	519 ms	468 KiB

knapsack

#include "bits/stdc++.h"
using namespace std;
#define SorSufi namespace
#define ll long long
#define all(a) a.begin(), a.end()
#define popcount(x) __builtin_popcountll(x)
#define ctz(x) __builtin_ctzll(x)
#define clz(x) __builtin_clzll(x)
#define lsb(x) (x & -x)
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<ll,ll>
// #define cerr cout
#define int ll
#define endl '\n'
// #define TIME (1.0 * clock() / CLOCKS_PER_SEC)

bool minimize(int &x, int y) { return x > y ? x = y, 1 : 0; }
bool maximize(int &x, int y) { return x < y ? x = y, 1 : 0; }

SorSufi Fexin{
    struct Node{int w, v, sl;};

    const int N = 2e3;
    int n, S, dp[N + 5];
    Node item;

    void Merlin(){
        cin >> S >> n;
        for (int i = 1; i <= n;++i){
            cin >> item.v >> item.w >> item.sl;
            for (int k = 0; item.sl;++k){
                int take = min(1ll << k, item.sl);
                int w = item.w * take, v = item.v * take;

                for (int s = S; s >= w;--s)maximize(dp[s], dp[s - w] + v);

                item.sl -= take;

            }
        }

        cout << dp[S];
    }
}

void Merlin() { Fexin::Merlin(); }

signed main(){
    #define FILE_NAME "main"
    ios_base::sync_with_stdio(0);cin.tie(0);

    if (fopen(FILE_NAME ".in", "r")){
        freopen(FILE_NAME ".in", "r", stdin);
        freopen(FILE_NAME ".out", "w", stdout);
    }

    if (fopen(FILE_NAME ".inp", "r")){
        freopen(FILE_NAME ".inp", "r", stdin);
        freopen(FILE_NAME ".out", "w", stdout);
    }

    // int tc;cin >> tc;while(tc--)
    Merlin();
    // cerr << "TIME PROCCESS: " << TIME;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         freopen(FILE_NAME ".in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:55:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         freopen(FILE_NAME ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:59:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         freopen(FILE_NAME ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:60:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         freopen(FILE_NAME ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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