Submission #1163664

#TimeUsernameProblemLanguageResultExecution timeMemory
1163664ramalzaherKnapsack (NOI18_knapsack)C++20
73 / 100
281 ms4284 KiB
#include <bits/stdc++.h> #define int long long using namespace std; const int N = 10000000; int dp[N], w[N], v[N] , k[N]; void solve() { int n, m; cin >> m >> n; vector<pair<int,int>> v2; for (int i = 0; i < n; i++) { cin >> v[i] >> w[i] >> k[i]; v2.push_back({w[i]/v[i],i}); } sort(v2.begin(),v2.end(),greater<pair<int,int>>()); dp[0] = 0;int C = 9000;C=min(C , n); for (int c = 0; c <C; c++) { int i = v2[c].second; for (int j = m; j > 0; j--) { int z = 1; while (j - z*w[i] >= 0 && z<=k[i]) { dp[j] = max( dp[j], (dp[j - z * w[i]] + z * v[i])); z++; } } } cout << dp[m] << endl; } main() { // #ifndef ONLINE_JUDGE // freopen(".in", "r", stdin); // freopen(".out", "w", stdout); // #endif ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int tt = 1; // cin >> tt; while (tt--) { solve(); } return 0; }

Compilation message (stderr)

knapsack.cpp:34:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   34 | main()
      | ^~~~
#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...