Submission #5942211

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using LL  = long long;
using VI  = vector<LL>;
using VVI = vector<VI>;
using VB  = vector<bool>;
using VS  = vector<string>;
using PII = pair<LL, LL>;
using VP  = vector<PII>;
#define PB           push_back
#define MP           make_pair
#define SZ(a)        LL((a).size())
#define EACH(x, c)   for (auto x : (c))
#define ALL(c)       (c).begin(), (c).end()
#define REVERSE(c)   reverse(ALL(c))
#define SORT(c)      stable_sort(ALL(c))
#define RSORT(c)     stable_sort((c).rbegin(), (c).rend())
#define FSORT(c)     stable_sort(ALL(c), [] (auto& x, auto& y) {return x.first < y.first;});
#define FRSORT(c)    stable_sort(ALL(c), [] (auto& x, auto& y) {return x.first > y.first;});
#define SSORT(c)     stable_sort(ALL(c), [] (auto& x, auto& y) {return x.second < y.second;});
#define SRSORT(c)    stable_sort(ALL(c), [] (auto& x, auto& y) {return x.second > y.second;});
#define FOR(i, a, b) for (LL i = (a); i < (b); ++i)
#define REP(i, n)    FOR(i, 0, n)
#define $(x) {cout << #x << " = " << (x) << endl;}

LL knapsackZeroOne(LL N, LL W, VI& weight, VI& value) {   // weight & value must be 1-indexed
    VVI dp(N + 1, VI(W + 1));   // dp[i][j] = max value sum with weight <= j using up to i-th objects
    FOR(i, 1, N + 1) {
        REP(j, W + 1) {
            dp[i][j] = max(dp[i][j], dp[i - 1][j]);   // don't use object i
            if (j - weight[i] >= 0) dp[i][j] = max(dp[i][j], dp[i - 1][j - weight[i]] + value[i]);   // use object i
        }
    }
    return dp[N][W];
}

LL knapsackUnbounded(LL N, LL W, VI& weight, VI& value) {   // weight & value must be 1-indexed
    VVI dp(N + 1, VI(W + 1));   // dp[i][j] = max value sum with weight <= j using up to i-th objects
    FOR(i, 1, N + 1) {
        REP(j, W + 1) {
            dp[i][j] = max(dp[i][j], dp[i - 1][j]);   // don't use object i
            if (j - weight[i] >= 0) dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);   // use object i
        }
    }
    return dp[N][W];
}

int main() {
    LL N;
    cin >> N;
    VVI R(2, VI(3 + 1));
    REP(i, 2) {
        FOR(j, 1, 3 + 1) {
            cin >> R[i][j];
        }
    }

    VI weight(3 + 1), value(3 + 1);
    FOR(i, 1, 3 + 1) {
        weight[i] = R[0][i];
        value[i] = R[1][i] - R[0][i];   // consider the difference (how many N increases)
    }
    N += knapsackUnbounded(3, N, weight, value);   // A -> B
    FOR(i, 1, 3 + 1) {
        weight[i] = R[1][i];
        value[i] = R[0][i] - R[1][i];   // consider the difference (how many N increases)
    }
    N += knapsackUnbounded(3, N, weight, value);   // B -> A

    cout << N << endl;
	
    return 0;
}

Submission Info

Judge Result