# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
489571 | 2021-11-23T09:33:28 Z | vicyan1611 | Knapsack (NOI18_knapsack) | C++14 | 24 ms | 31692 KB |
#include <bits/stdc++.h> using namespace std; const long long oo = 1e18 + 7; int s, n; long long f[2002][2002]; vector <pair <int, int>> ite[2002]; int main() { cin >> s >> n; for (int i = 1; i <= n; ++i) { int v, w, k; cin >> v >> w >> k; if (w > s || k <= 0) continue; ite[w].push_back(make_pair(v, k)); } for (int i = 0; i <= s; ++i) { for (int j = 0; j <= s; ++j) { f[i][j] = -oo; } } f[0][0] = 0; int countid = 1; for (int id = 1; id <= s; ++id) { if (!ite[id].size()) continue; sort(ite[id].begin(), ite[id].end(), greater <pair <int, int>>()); for (int w = 0; w <= s; ++w) { int idt = 0; int copies = 0; int prof = 0; int cnt = 0; while ((copies + 1) * id <= w && idt < ite[id].size()) { copies++; prof += ite[id][idt].first; if (f[countid - 1][w - copies * id] != -oo) { f[countid][w] = max(f[countid][w], f[countid - 1][w - copies * id] + prof); } cnt++; if (cnt == ite[id][idt].second) { idt++; cnt = 0; } } } countid++; } long long res = 0; for (int i = 0 ; i <= s; ++i) { for (int j = 0; j <= s; ++j) { res = max(res, f[i][j]); } } cout << res; return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 17136 KB | Output is correct |
2 | Correct | 10 ms | 17100 KB | Output is correct |
3 | Correct | 13 ms | 17228 KB | Output is correct |
4 | Correct | 10 ms | 17228 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 332 KB | Output is correct |
2 | Correct | 19 ms | 31692 KB | Output is correct |
3 | Correct | 18 ms | 31692 KB | Output is correct |
4 | Incorrect | 24 ms | 31564 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 332 KB | Output is correct |
2 | Correct | 19 ms | 31692 KB | Output is correct |
3 | Correct | 18 ms | 31692 KB | Output is correct |
4 | Incorrect | 24 ms | 31564 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 17136 KB | Output is correct |
2 | Correct | 10 ms | 17100 KB | Output is correct |
3 | Correct | 13 ms | 17228 KB | Output is correct |
4 | Correct | 10 ms | 17228 KB | Output is correct |
5 | Correct | 0 ms | 332 KB | Output is correct |
6 | Correct | 19 ms | 31692 KB | Output is correct |
7 | Correct | 18 ms | 31692 KB | Output is correct |
8 | Incorrect | 24 ms | 31564 KB | Output isn't correct |
9 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 17136 KB | Output is correct |
2 | Correct | 10 ms | 17100 KB | Output is correct |
3 | Correct | 13 ms | 17228 KB | Output is correct |
4 | Correct | 10 ms | 17228 KB | Output is correct |
5 | Correct | 0 ms | 332 KB | Output is correct |
6 | Correct | 19 ms | 31692 KB | Output is correct |
7 | Correct | 18 ms | 31692 KB | Output is correct |
8 | Incorrect | 24 ms | 31564 KB | Output isn't correct |
9 | Halted | 0 ms | 0 KB | - |