Submission #995259

#	Time	Username	Problem	Language	Result	Execution time	Memory
995259		gmroh06	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	63 ms	129624 KiB

ho_t3

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

inline void fastio() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

const ll INF = 0x3f3f3f3f3f3f3f3f;

ll n, l, ans;
ll arr[202], t[202];
ll cdp[202][202][202], rdp[202][202][202]; // 시계, 반시계, 개수

int main() {
    fastio();

    cin >> n >> l;

    for (ll i = 1; i <= n; i++) {
        cin >> arr[i];
    }

    arr[n + 1] = l;

    for (ll i = 1; i <= n; i++) {
        cin >> t[i];
    }

    memset(cdp, 0x3f, sizeof(cdp));
    memset(rdp, 0x3f, sizeof(rdp));

    for (ll i = 0; i <= n; i++) {
        for (ll j = n + 1; j > i; j--) {
            for (ll k = 0; k <= n; k++) {
                if (i == 0 and j == n + 1 and k == 0) {
                    cdp[i][j][k] = rdp[i][j][k] = 0;
                }

                ll& x = cdp[i][j][k];

                if (i > 0) {
                    ll ct = arr[i] - arr[i - 1], rt = l - arr[j] + arr[i];

                    if (k > 0 and cdp[i - 1][j][k - 1] + ct <= t[i]) x = min(x, cdp[i - 1][j][k - 1] + ct);
                    if (cdp[i - 1][j][k - 1] + ct > t[i]) x = min(x, cdp[i - 1][j][k] + ct);

                    if (k > 0 and rdp[i - 1][j][k - 1] + rt <= t[i]) x = min(x, rdp[i - 1][j][k - 1] + rt);
                    if (rdp[i - 1][j][k - 1] + rt > t[i]) x = min(x, rdp[i - 1][j][k] + rt);
                }

                ll& y = rdp[i][j][k];

                if (j <= n) {
                    ll rt = arr[j + 1] - arr[j], ct = l - arr[j] + arr[i];

                    if (k > 0 and rdp[i][j + 1][k - 1] + rt <= t[j]) y = min(y, rdp[i][j + 1][k - 1] + rt);
                    if (rdp[i][j + 1][k - 1] + rt > t[j]) y = min(y, rdp[i][j + 1][k] + rt);

                    if (k > 0 and cdp[i][j + 1][k - 1] + ct <= t[j]) y = min(y, cdp[i][j + 1][k - 1] + ct);
                    if (cdp[i][j + 1][k - 1] + ct > t[j]) y = min(y, cdp[i][j + 1][k] + ct);
                }

                if (ans < k) {
                    if (x != INF) ans = k;
                    if (y != INF) ans = k;
                }
            }
        }
    }

    cout << ans;

    return 0;
}

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