Submission #1262856

#TimeUsernameProblemLanguageResultExecution timeMemory
1262856khanghb2006Knapsack (NOI18_knapsack)C++20
73 / 100
1092 ms1604 KiB
#include<bits/stdc++.h> using namespace std; #define TASK "task" const int mxN = 5e5 + 7; const int inf = 1e9 + 67; struct item { int w , v , k; }a[mxN]; int n; int S; long long sum = 0; long long dp[3000]; void solve(void) { cin >> S >> n; for (int i = 1; i <= n; i++) { cin >> a[i].v >> a[i].w >> a[i].k; if(!a[i].w) sum += a[i].v * a[i].k; } for (int i = 0; i <= S; i++) dp[i] = sum; for (int i = 1; i <= n; i++) { if(a[i].w == 0) continue; int c = 1; while(a[i].k > 0) { int can = min(c , a[i].k); long long W = 1LL * can * a[i].w; long long V = 1LL * can * a[i].v; for (int j = S; j >= W; j--) dp[j] = max(dp[j] , dp[j - W] + V); a[i].k -= can; c *= 2; } } long long ans = -inf; for (int i = 0; i <= S; i++) ans = max(ans , dp[i]); cout << ans; } int main() { ios_base :: sync_with_stdio(0); cin.tie(0); //freopen(TASK".inp","r",stdin); //freopen(TASK".out","w",stdout); int tc = 1; //cin >> tc; while(tc--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...