Submission #572947

#	Time	Username	Problem	Language	Result	Execution time	Memory
572947		BenyKarimi	Knapsack (NOI18_knapsack)	C++17	73 / 100	26 ms	33236 KiB

knapsack

#include<bits/stdc++.h>

#define For(i, x, n) for(int i = x; i < n; i++)
#define Rof(i, x, n) for(int i = n - 1; i >= x; i--)

#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define F first
#define S second
#define pb push_back
#define po pop_back
#define En endl
#define endl "\n"

#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend();

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<PLL> VPLL;

const int MN = 2e3 + 5;
const int MOD = 1e9 + 7;
const int LOG = 20;
const LL INF = 1e18 + 7;

LL s, n, v, maxw;
LL dp[MN][MN], k[MN], w[MN];
VLL keep[MN];

int main () {
    IOS;
    cin >> s >> n;

    VPLL forsort;
    For (i, 0, n) {
        cin >> v >> w[i] >> k[i];
        maxw = max(maxw, w[i]);
        forsort.pb({v, i});
    }

    sort(ALL(forsort));
    reverse(ALL(forsort));

    for (PII it : forsort) {
        For (i, 0, k[it.S]) {
            if (keep[w[it.S]].size() == MN - 5) break;
            keep[w[it.S]].pb(it.F);
        }       
    }

    For (i, 0, maxw + 1) {
        For (j, 1, s + 1) dp[i][j] = -INF;
    }

    For (i, 1, maxw + 1) {
        For (j, 1, s + 1) {
            dp[i][j] = dp[i - 1][j];

            LL sum = 0;
            For (k, 0, keep[i].size()) {
                sum = sum + keep[i][k];
                LL jon = 1ll * (k + 1) * i;
                if (jon > j) break;
                dp[i][j] = max(dp[i][j], dp[i - 1][j - jon] + sum);
            }
        }
    }

    LL ans = 0;
    For (j, 0, s + 1) ans = max(ans, dp[maxw][j]);
    cout << ans << En;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:3:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define For(i, x, n) for(int i = x; i < n; i++)
......
   66 |             For (k, 0, keep[i].size()) {
      |                  ~~~~~~~~~~~~~~~~~~~~  
knapsack.cpp:66:13: note: in expansion of macro 'For'
   66 |             For (k, 0, keep[i].size()) {
      |             ^~~

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 0 / 27