제출 #1306079

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306079		vespasian_1	Knapsack (NOI18_knapsack)	C++20	73 / 100	1095 ms	2792 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],x/w[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;
 cout << "\n";
 return 0;
}

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