Submission #1228450

#TimeUsernameProblemLanguageResultExecution timeMemory
1228450mn3mKnapsack (NOI18_knapsack)C++20
73 / 100
461 ms4308 KiB
#pragma GCC optimize ("O3") #pragma GCC optimize ("unroll-loops") #pragma GCC optimize("-Ofast") #include<bits/stdc++.h> #define int long long #define pb push_back #define ceil(x,y) (x/y)+(x%y!=0)*((double)(1.0*x/y)<0?0:1) using namespace std; int MOD = 998244353; int MX = 1e15; int MN = -1e15; int s, n; int v[100002], w[100002], k[100002]; int dp[102][2002]; int slv(int idx,int cur) { if (cur < 0) return -10000000000000; if (cur == 0 || idx == n) return 0; int& ret = dp[idx][cur]; if (ret != -1) return ret; for (int i = 0; i <= min(k[idx],cur/w[idx]);i++) ret=max(ret,slv(idx+1,cur-w[idx]*i)+v[idx]*i); return ret; } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("snakes.in","r",stdin); // freopen("snakes.out","w",stdout); int T = 1; // cin >> T; while (T--) { cin >> s >> n; for (int i = 0; i < n; i++) cin >> v[i] >> w[i] >> k[i]; memset(dp, -1, sizeof(dp)); cout << slv(0, s); } 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...