Submission #684822

#	Time	Username	Problem	Language	Result	Execution time	Memory
684822		Farhan_HY	Knapsack (NOI18_knapsack)	C++14	0 / 100	112 ms	262144 KiB

knapsack

#include <bits/stdc++.h>
//#define int long long
#define F first
#define S second
#define T int t;cin>>t;while(t--)
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int N = 1e5 + 6;
const int M = 2005;
const int mod = 1e9 + 7;
int dp[N][M];
int w[N], v[N], k[N], n, s;

int Rec(int i, int j) {
    if (i > n) return 0;
    int &ret = dp[i][j];
    if (ret != -1) return ret;
    for(int u = 0; u <= k[i]; u++) {
        if (j + u * w[i] > s) break;
        ret = max(ret, Rec(i + 1, j + u * w[i]) + u * v[i]);
    }
    return ret;
}

main() {
    IOS
    cin >> s >> n;
    for(int i = 1; i <= n; i++)
        cin >> v[i] >> w[i] >> k[i];
    memset(dp, -1, sizeof dp);
    cout << Rec(1, 0);
}

Compilation message (stderr)

knapsack.cpp:25:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   25 | main() {
      | ^~~~

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