Submission #1306078

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306078		vespasian_1	Knapsack (NOI18_knapsack)	C++20	0 / 100	1 ms	568 KiB

knapsack

#include<bits/stdc++.h>
#define v vector
using namespace std;
typedef long long let;
int main(){
 ios_base::sync_with_stdio(false);
 cin.tie(nullptr);
 let x,n;
 cin >> x >> n;
 v<let> c(n);
 v<let> w(n);
 v<let> t(n);
 for(let i = 0;i<n;i++)cin >> c[i] >> w[i] >> t[i];
 v<let> sum(x+1,0);
 for(let i = 0;i<n;i++) t[i] = min(t[i],2000/c[i]);
 for(let i =0;i<n;i++){
  for(let j =0;j<t[i];j++){
   for(let l = x;l>=w[i];l--){
    sum[l] = max(sum[l], sum[l-w[i]]+c[i]);
   }
  }
 }
 let out = 0;
 for(let i = 0;i<=x;i++){
  out = max(out, sum[i]);
 }
 cout << out;
 return 0;
}

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