Submission #1137159

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137159		hoa208	Knapsack (NOI18_knapsack)	C++20	37 / 100	1 ms	328 KiB

knapsack

#include <bits/stdc++.h>
#pragma GCC("Ofast")
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
using namespace std;
#define ll  long long
#define db  double
#define vl  vector<ll>
#define pll  pair<ll, ll>
#define vpll  vector<pll>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b))
#define BIT(x, i) (((x) >> (i)) & 1) 

#define PROBLEM "test"

int dx[] = {-1, 0, 1, 0, -1, -1, 1, 1};
int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
const int mod[] = {(int)1e9 + 2277, (int)1e9 + 5277, (int)1e9 + 8277, (int)1e9+ 9277};
const double eps = 1e-9;
const int LOG = 17;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;

// ---------------------------------------- 

void solve() {
    int n, m;
    cin >> m >> n;

    vector<int> w, v;
    w.pb(0), v.pb(0);
    for(int i = 1; i <= n; i++) {
        int W, V, a;
        cin >> V >> W>> a;

        int pw = 1;
        while(a >= pw) {
            a -= pw;
            w.pb(W * pw);
            v.pb(V * pw);
            pw <<= 1;
        }

        if(a > 0) 
            w.pb(W * a), v.pb(V * a);
    }

    int dp[m + 1];
    memset(dp, 0, sizeof(dp));
    n = w.size() - 1;
    for(int i = 1; i <= n; i++) 
        for(int j = m; j >= 0; j--)
            if(j >= w[i])
                dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

    cout << dp[m] << '\n';
}

int main(){ 
    ios_base::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);
    if (fopen(PROBLEM".inp", "r")){
        freopen(PROBLEM".inp", "r", stdin);
        freopen(PROBLEM".out", "w", stdout);
    }
    bool ok = false;
    if(ok) {
        int t; cin >> t;
        while(t--)  solve();
    }   
    else
        solve();
}

Compilation message (stderr)

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

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