Submission #541301

#	Time	Username	Problem	Language	Result	Execution time	Memory
541301		eulerdesoja	Knapsack (NOI18_knapsack)	C++17	100 / 100	217 ms	35216 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;

void setIO(string s) {
    ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
     freopen((s+ ".in").c_str(),"r",stdin);
    freopen((s+".out").c_str(),"w",stdout);
}

#define int long long
#define pb push_back
#define sz(x) (int)x.size()
#define endl "\n"

typedef pair<int,int>ii;
typedef vector<int> vi;

const int mxn = 2e3 + 5;
int dp[mxn][mxn], s, n;

vector<ii> p[mxn];

int cnt(int i, int cap) {
    if (i == s + 1 || cap == 0) return 0;

    int &ans = dp[i][cap];
    if (ans != -1)return ans;

    int w_sum = 0, v_sum = 0;
    ans = 0;
    ans = max(ans, cnt(i + 1, cap));

    for (ii cur: p[i]) {
        if (w_sum + i > cap)break;
        int qtd = cur.second;
        while(qtd-- && w_sum + i <= cap) {
            w_sum += i;
            v_sum += cur.first;
            //cout<<i<<" "<<w_sum<<" "<<v_sum<<"\n";
            ans = max(ans, cnt(i + 1, cap - w_sum) + v_sum);
        }
    }
    return ans;
}

void solve() {
    cin>>s>>n;

    for (int i = 0; i < n; i++) {
        int v, w, k;cin>>v>>w>>k;
        p[w].pb({v, k});
    }

    for (int i = 0; i < mxn; i++)sort(p[i].begin(), p[i].end(), greater<ii>());

    // for (int i = 0; i < mxn;i++)if(sz(p[i])) {
    //     for (ii j: p[i])cout<<j.first<<" "<<j.second<<" ";
    //     cout<<"\n";
    // }

    memset(dp, -1, sizeof(dp));
    cout<<cnt(1, s)<<"\n";


}

int32_t main(void) {
    ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
    //setIO("convention");

    int t = 1;
    //cin>>t;

    while(t--) solve();
}

Compilation message (stderr)

knapsack.cpp: In function 'void setIO(std::string)':
knapsack.cpp:6:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 |      freopen((s+ ".in").c_str(),"r",stdin);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:7:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |     freopen((s+".out").c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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