Official

G - Get Many Cola Editorial by en_translator

Let \(D_i=A_i-B_i\) and \(K=\max_i A_i\).

If there are multiple \(i\) with the same values of \(A_i\), it is useless to use only the one with the maximum \(B_i\), and we can simply remove the others. Now we can assume that \(M\leq K\).

By interpreting the problem in reverse order, the problem can be represented as follows:

  • Initially, your score is \(N\).
  • Choose any integer \(x\ (0\leq x\leq N)\) and repeat the following:
    • Choose an \(i\) with \(x\geq B_i\) and \(x+D_i\leq N\), add \(D_i\) to \(x\), and add \(B_i\) to the score.
  • Find the maximum possible score.

This is similar to the unbounded knapsack problem with weight \(D_i\), value \(B_i\), and capacity \(N\). (Indeed, after reaching \(x\geq K\) it is identical to the knapsack problem.) Thus, the popular tricks applicable for ordinary knapsack problems can be adopted to our problem too. Analogous to the knapsack problem, let us call an operation against an \(i\) “use an item \(i\).”

Let \(i'\) be (one of) the \(i\) with the largest \(\frac{B_i}{D_i}\). In fact, we can prove that there exists an optimal solution where the sum of \(D_i\) over all used items other than item \(i'\) (where repeated use of the same items contributes to the sum multiple times) is less than \(K(K+1)\).

Proof

Assume that the sum of $D_i$ over the used items other than item $i'$ is $K(K+1)$ or greater.

First, consider the moment at which $x$ has become $K$ or greater for the first time. Since it useless to set the initial $x$ to greater than $K$, so we assume that $x$ has become between $K$ (inclusive) and $2K$ (exclusive). After this moment, we do not have to care about the condition $x\geq B_i$.

By assumption, the sum of $D_i$ over all items used afterward other than item $i'$ is at least $K(K+1)-(2K-1)=K(K-1)+1$, so at least $K$ items are used. Let $S_j\ (0\leq j\leq K)$ be the sum of $D_i$ over the first $j$ items among them. By pigeonhole principle, there exist $0\leq l < r\leq K$ with $S_l\equiv S_r\ (\bmod\ D_{i'})$. Instead of using items $l+1,l+2,\dots,r$, we may use item $i'$ $\frac{S_r-S_l}{D_{i'}}$ times.

Hence, it is sufficient to perform the DP (Dynamic Programming) in the same manner as the ordinary knapsack problem, and from then only consider using item \(i'\).

The computational complexity is \(O(M+K^3)\).

Sample code (C++):

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int MAX_A = 310;

int main() {
    ll n;
    int m;
    cin >> n >> m;
    vector<int> mx_b(MAX_A);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        mx_b[a] = max(mx_b[a], b);
    }
    vector<pair<int, int>> ls;
    for (int i = 0; i < MAX_A; i++) {
        if (mx_b[i]) {
            ls.emplace_back(i - mx_b[i], mx_b[i]);
        }
    }
    int sz = MAX_A * (MAX_A + 1) + 10;
    vector<int> dp(sz);
    for (int i = 0; i < dp.size(); i++) {
        for (auto [w, v]: ls) {
            if (i < v or i + w >= dp.size()) continue;
            dp[i + w] = max(dp[i + w], dp[i] + v);
        }
    }
    if (n < dp.size()) {
        cout << n + dp[n] << endl;
        return 0;
    }
    for (int i = 1; i < ls.size(); i++) {
        if (ls[0].second * ls[i].first < ls[0].first * ls[i].second) {
            swap(ls[0], ls[i]);
        }
    }
    auto [w, v] = ls[0];
    ll ans = 0;
    for (int i = MAX_A; i < dp.size(); i++) {
        ll now = dp[i] + (n - i) / w * v;
        ans = max(ans, now);
    }
    cout << n + ans << endl;
}

posted:
last update: