Submission #1027417

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027417		Robert_junior	Knapsack (NOI18_knapsack)	C++17	73 / 100	1096 ms	472 KiB

knapsack

#pragma GCC target ("avx2")
#pragma GCC optimize ("Ofast")
#include <iostream>
#include <vector>
using namespace std;
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz size()
#define ins insert
void solve(){
    int m, n;
    cin>>m>>n;
    vector<int>dp(m + 1);
    vector<int>dp1(m + 1);
    int a, b, c;
    for(int i = 1; i <= n; ++i){
        cin>>a>>b>>c;
        for(int j = 0; j <= m; ++j){
            dp1[j] = dp[j];
        }
        for(int j = 0; j <= m; ++j){
            for(int k = 1; k <= c && j + b * k <= m; ++k){
                dp[j + b * k] = max(dp[j + b * k], dp1[j] + k * a);
            }
        }
    }
    int mx = 0;
    for(int i = 0; i <= m; i++) mx = max(mx, dp[i]);
    cout<<mx<<'\n';
}
main(){
    //freopen("circlecross.in", "r", stdin);
    //freopen("circlecross.out", "w", stdout);
	ios_base :: sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int t = 1;
	//cin>>t;
	while(t--){
		solve();
	}
}
//3 2 4 4 1 3 2 1

Compilation message (stderr)

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

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