Help Needed
Разница между en1 и en2, 77 символ(ов) изменены
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 &mdash; 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 &mdash; 1][j &mdash; total]);↵
                } else {↵
                    temp += (j &mdash; total) / i * u.first;↵
                    total += (j &mdash; total) / i * i;↵
                    f[i][j] = max(f[i][j], temp + f[i &mdash; 1][j &mdash; total]);↵
                    break;↵
                }↵
            }↵
            f[i][j] = max(f[i][j], temp + f[i &mdash; 1][j &mdash; 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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
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)