Submission #1011179

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011179		mizunokaze	Knapsack (NOI18_knapsack)	C++14	37 / 100	1065 ms	604 KiB

knapsack

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define F first
#define S second
using namespace std;
int dp[2005];

struct Kn{
    int v, w, k;
} kn[100005];

void solve(){
   int S, N;
   cin >> S >> N;
   for(int i =1 ; i <= N; i ++) cin >> kn[i].v >> kn[i].w >> kn[i].k;
   dp[0] = 0;

   for(int i = 1; i <= N; i ++){
        for(int j = 1; j <= kn[i].k; j ++){
            for(int l = S; l >= kn[i].w; l --){
                dp[l] = max(dp[l], dp[l - kn[i].w] + kn[i].v);
            }
        }
   }
   cout << dp[S];
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
    solve();
}

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