Submission #1183207

#TimeUsernameProblemLanguageResultExecution timeMemory
1183207chikien2009Knapsack (NOI18_knapsack)C++20
100 / 100
608 ms47912 KiB
#include <bits/stdc++.h> using namespace std; void setup() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); } int n, s, a, b, c; priority_queue<int> pq[2001]; long long v[2001][2001], f[2001]; int main() { setup(); cin >> s >> n; for (int i = 0; i < n; ++i) { cin >> a >> b >> c; while (c--) { pq[b].push(-a); if (pq[b].size() > s) { if (pq[b].top() == -a) { c = 0; } pq[b].pop(); } } } for (int i = 0; i <= s; ++i) { while (!pq[i].empty()) { v[i][pq[i].size()] = -pq[i].top(); pq[i].pop(); } for (int j = 1; j <= s; ++j) { if (v[i][j] == 0) { v[i][j] = -1; continue; } v[i][j] += v[i][j - 1]; } } fill_n(f, s + 1, -1); f[0] = 0; for (int i = 1; i <= s; ++i) { for (int j = s; j >= 0; --j) { if (f[j] != -1) { for (int k = 1; j + k * i <= s && v[i][k] != -1; ++k) { f[j + k * i] = max(f[j + k * i], f[j] + v[i][k]); } } } } cout << (*max_element(f, f + s + 1)); 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...