Submission #1036241

#TimeUsernameProblemLanguageResultExecution timeMemory
1036241sh1roKnapsack (NOI18_knapsack)C++14
0 / 100
136 ms262144 KiB
#include <bits/stdc++.h> #define int long long #define endl '\n' using namespace std; const int N = 1e5 + 4; const int oo = 1e18; const int mod = 1e9 + 7; int t, n, q, m, k, a[N], ans, dp[N][2005], w, cnt, cur, dem, coun, profit; map<int, vector<pair<int, int>>>mp; vector<pair<int, int>>v; bool cmp(pair<int, int>a, pair<int, int>b){ return a.first > b.first; } void solve(){ cnt = 1; cin >> k >> n; for (int i = 1; i <= n; i++){ int x, y, z; cin >> x >> y >> z; if (y <= k)mp[y].push_back({x, z}); } memset(dp, -1, sizeof(dp)); dp[0][0] = 0; for (auto p : mp){ w = p.first, v = p.second; sort(v.begin(), v.end(), cmp); for (int i = 0; i <= k; i++){ dem = coun = 0, cur = 1; dp[cnt][i] = dp[cnt - 1][i]; profit = 0; while (cur * w <= i && dem < v.size()){ profit += v[dem].first; if (dp[cnt - 1][i - cur * w] != -1)dp[cnt][i] = max(dp[cnt][i], dp[cnt - 1][i - cur * w] + profit); cur++; coun++; if (coun == v[dem].second){ coun = 0; dem++; } } } cnt++; } for (int i = 0; i <= n; i++){ for (int j = 0; j <= k; j++)ans = max(ans, dp[i][j]); } cout << ans; } main() { ios_base::sync_with_stdio(false); cin.tie(NULL); //freopen("clocktree.in", "r", stdin); freopen("clocktree.out", "w", stdout); t = 1; //cin >> t; while (t--)solve(); return 0; }

Compilation message (stderr)

knapsack.cpp: In function 'void solve()':
knapsack.cpp:30:40: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |             while (cur * w <= i && dem < v.size()){
      |                                    ~~~~^~~~~~~~~~
knapsack.cpp: At global scope:
knapsack.cpp:48:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   48 | 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...