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 summary="Spoiler">↵
#pragma GCC optimize("Ofast,unroll-loops")↵
#pragma GCC target("avx,avx2,fma")↵
↵
#include <bits/stdc++.h>↵
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();↵
}↵
</spoiler>↵
↵
Sorry about the bad format of the code, I don't know how to make it better.
↵
<spoiler summary="Spoiler">↵
#pragma GCC optimize("Ofast,unroll-loops")↵
#pragma GCC target("avx,avx2,fma")↵
↵
#include <bits/stdc++.h>↵
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();↵
}↵
</spoiler>↵
↵
Sorry about the bad format of the code, I don't know how to make it better.
