Submission #591535

#	Time	Username	Problem	Language	Result	Execution time	Memory
591535		piOOE	Collecting Stamps 3 (JOI20_ho_t3)	C++17	15 / 100	105 ms	127468 KiB

ho_t3

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 201;

ll dp[2][N][N][N];
int L[N], R[N], TR[N], TL[N];

void ckmin(ll &a, ll b) {
    if (a == -1 || a > b) {
        a = b;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, p;
    cin >> n >> p;
    for (int i = 0; i < n; ++i) {
        cin >> R[i];
        L[n - i - 1] = p - R[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> TR[i];
        TL[n - i - 1] = TR[i];
    }
    memset(dp, -1, sizeof(dp));
    //0 - in the left, 1 - in the right
    if (R[0] <= TR[0]) {
        dp[1][0][1][1] = R[0];
    } else {
        dp[1][0][1][0] = R[0];
    }
    if (L[0] <= TL[0]) {
        dp[0][1][0][1] = L[0];
    } else {
        dp[0][1][0][0] = L[0];
    }
    for (int sum = 1; sum < n; ++sum) {
        for (int f = 0; f <= sum; ++f) {
            int s = sum - f;
            for (int cnt = 0; cnt <= n; ++cnt) {
                if (dp[0][f][s][cnt] != -1) {
                    assert(f);
                    int t = dp[0][f][s][cnt];
                    int dist = L[f] - L[f - 1] + t;
                    ckmin(dp[0][f + 1][s][cnt + (dist <= TL[f])], dist);
                    dist = R[s] + L[f - 1] + t;
                    ckmin(dp[1][f][s + 1][cnt + (dist <= TR[s])], dist);
                }
                if (dp[1][f][s][cnt] != -1) {
                    assert(s);
                    int t = dp[1][f][s][cnt];
                    int dist = R[s - 1] + L[f] + t;
                    ckmin(dp[0][f + 1][s][cnt + (dist <= TL[f])], dist);
                    dist = t + R[s] - R[s - 1];
                    ckmin(dp[1][f][s + 1][cnt + (dist <= TR[s])], dist);
                }
            }
        }
    }
    for (int cnt = n; cnt >= 0; --cnt) {
        for (int sum = n; sum > 0; --sum) {
            for (int f = 0; f <= sum; ++f) {
                int s = sum - f;
                if (dp[0][f][s][cnt] != -1 || dp[1][f][s][cnt] != -1) {
                    cout << cnt;
                    return 0;
                }
            }
        }
    }
    cout << 0;
    return 0;
}

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