Submission #1257887

#TimeUsernameProblemLanguageResultExecution timeMemory
1257887limon4ickKnapsack (NOI18_knapsack)C++20
29 / 100
2 ms328 KiB
/*#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3") #pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") #pragma GCC optimization("unroll-loops") #pragma ("reroll") */ #include <bits/stdc++.h> using namespace std; #define int long long #define pb push_back #define ins insert #define F first #define S second const int mod = 1e7 + 7,N = 2100; int dp[N]; signed main(){ //freopen("justcoding.in","r",stdin); //freopen("justcoding.out","w",stdout); std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n,s; cin >> s >> n; int v[n + 1],w[n + 1],k[n + 1]; for(int i = 1;i<=n;i++) cin >> v[i] >> w[i] >> k[i]; if(n==1){ int sum = 0; int ans = 0; while(sum+w[1]<=s && k[1]){ sum+=w[1]; k[1]--; ans+=v[1]; } cout << ans; return 0; } for(int i = 1;i<N;i++) dp[i] = -INT_MAX; if(n<=100){ for(int i = 1;i<=n;i++){ for(int x = s;x>=0;x--){ int y = k[i]; int xz = x; while(y-- && xz+w[i]<=s){ xz+=w[i]; if(dp[x]>=0) dp[xz] = max(dp[x]+v[i],dp[xz]); } } } int ans = 0; for(int i = 0;i<=s;i++){ ans = max(ans,dp[i]); } cout << ans; } }
#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...