Submission #575158

#	Time	Username	Problem	Language	Result	Execution time	Memory
575158		erekle	Collecting Stamps 3 (JOI20_ho_t3)	C++17	25 / 100	229 ms	132904 KiB

ho_t3

#include <iostream>
#include <vector>

using namespace std;

const int N = 200;
const long long INF = 1e18;

long long dp[1+N][1+N][2][1+N];
// dp[l][r][p][s] is minimum time where:
//  - [l, r] is range of stamps left
//  - p is the current position (boolean - either l-1 or r+1)
//  - s is the current number of stamps collected

int main() {
    int n, L;
    cin >> n >> L;
    vector<int> x(1+n), t(1+n);
    for (int i = 1; i <= n; ++i) cin >> x[i];
    for (int i = 1; i <= n; ++i) cin >> t[i];
    x[0] = 0, t[0] = -1; // add stamp at x=0 that cannot be collected

    auto d = [&x, &n, &L](int i, int j) {
        if (i > j) swap(i, j);
        return min(x[j]-x[i], x[i]+L-x[j]);
    };

    // fill with INF
    for (int l = 0; l <= n; ++l) {
        for (int r = max(0, l-1); r <= n; ++r) {
            for (int p = 0; p <= 1; ++p) {
                for (int s = 0; s <= n; ++s) dp[l][r][p][s] = INF;
            }
        }
    }
   
    // addition of extra stamp makes base case easier
    dp[1][n][0][0] = dp[1][n][1][0] = 0;

    /* answers will be stored at sz = 0 (r = l-1), but we do not traverse
    since they are final states - they do not need to contribute to other states */

    // dp - pushing answers to later states rather than pulling from previous
    for (int sz = n; sz >= 1; --sz) {
        for (int l = 1; l+sz-1 <= n; ++l) {
            int r = l+sz-1, before = (l-1+(n+1))%(n+1), after = (r+1)%(n+1);
            for (int s = 0; s <= n; ++s) {
                // p = 0 means at l-1, p = 1 means at r+1
                for (int p = 0; p <= 1; ++p) { // current position
                    for (int p1 = 0; p1 <= 1; ++p1) { // next position
                        int cur = (!p ? before : after); // current location
                        int nxt = (!p1 ? l : r); // next location
                        long long time = dp[l][r][p][s] + d(cur, nxt); // total time taken
                        bool delta = time <= t[nxt]; // extra stamps collected (0 or 1)
                        
                        int l1 = l + (p1 == 0), r1 = r - (p1 == 1), s1 = s+delta;
                        if (r1 < 0) continue;
                        dp[l1][r1][p1][s1] = min(dp[l1][r1][p1][s1], time);
                    }
                }
            }
        }
    }

    int maxCollected = 0;
    for (int s = 1; s <= n; ++s) {
        for (int l = 1; l <= n; ++l) {
            if (dp[l][l-1][0][s] != INF || dp[l][l-1][1][s] != INF) {
                maxCollected = s;
            }
        }
    }
    cout << maxCollected << endl;
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 75