I have been trying to fix the bug in my code for this problem: https://oj.uz/problem/view/NOI18_knapsack. Any help would be very much appreciated.
Spoiler
Sorry about the bad format of the code, I don't know how to make it better.
# | User | Rating |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3741 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3489 |
7 | Radewoosh | 3483 |
8 | Kevin114514 | 3443 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 158 |
5 | -is-this-fft- | 158 |
7 | awoo | 156 |
8 | djm03178 | 155 |
9 | TheScrasse | 154 |
10 | Dominater069 | 153 |
Help Needed
I have been trying to fix the bug in my code for this problem: https://oj.uz/problem/view/NOI18_knapsack. Any help would be very much appreciated.
using namespace std;
typedef long long ll; const int MAX = 2002; vector<pair<ll, ll>> a[MAX]; ll f[MAX][MAX], s, n, u, v, w, k, total;
void solve() { cin >> s >> n; for (int i = 1; i <= n; i++) { cin >> v >> w >> k; a[w].push_back({v, k}); } for (int i = 1; i <= 2000; i++) sort(a[i].begin(), a[i].end(), greater<pair<ll, ll>>()); for (int i = 1; i <= s; i++) { for (int j = 1; j <= s; j++) { total = 0; ll temp = 0; f[i][j] = f[i — 1][j]; for (auto u : a[i]) { if (total + u.second * i <= j) { total += u.second * i; temp += u.second * u.first; f[i][j] = max(f[i][j], temp + f[i — 1][j — total]); } else { temp += (j — total) / i * u.first; total += (j — total) / i * i; f[i][j] = max(f[i][j], temp + f[i — 1][j — total]); break; } } f[i][j] = max(f[i][j], temp + f[i — 1][j — total]); //if (i > 19) cout << f[i][j] << " "; } //if (i > 19) cout << "\n"; } cout << f[s][s]; }
int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); solve(); }
Sorry about the bad format of the code, I don't know how to make it better.
Rev. | Lang. | By | When | Δ | Comment | |
---|---|---|---|---|---|---|
en3 | mustard_with_fries69420 | 2023-08-15 12:08:15 | 170 | |||
en2 | mustard_with_fries69420 | 2023-08-15 10:45:46 | 77 | |||
en1 | mustard_with_fries69420 | 2023-08-15 10:44:52 | 1727 | Initial revision (published) |
Name |
---|