제출 #390765

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
390765		timmyfeng	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	77 ms	64464 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;

const int N = 202, T = 1000000000;

int x[N], t[N], early[N][N][N][2];

void set_min(int &a, int b) {
    a = min(a, b);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, c;
    cin >> n >> c;

    for (int i = 1; i <= n; ++i) {
        cin >> x[i];
    }
    x[n + 1] = c;

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

    for (int l = 0; l <= n; ++l) {
        for (int r = 0; r <= n; ++r) {
            for (int i = 0; i <= n; ++i) {
                for (int j = 0; j < 2; ++j) {
                    early[l][r][i][j] = T + 1;
                }
            }
        }
    }

    early[0][0][0][0] = early[0][0][0][1] = 0;

    for (int i = 0; i < n; ++i) {
        for (int l = 0; l <= i; ++l) {
            int r = i - l, s;
            for (int j = 0; j <= i; ++j) {
                if (early[l][r][j][0] <= T) {
                    s = early[l][r][j][0] + x[l + 1] - x[l];
                    set_min(early[l + 1][r][j + (s <= t[l])][0], s);

                    s = early[l][r][j][0] + x[l] + c - x[n - r];
                    set_min(early[l][r + 1][j + (s <= t[n - 1 - r])][1], s);
                }

                if (early[l][r][j][1] <= T) {
                    s = early[l][r][j][1] + x[l + 1] + c - x[n + 1 - r];
                    set_min(early[l + 1][r][j + (s <= t[l])][0], s);

                    s = early[l][r][j][1] + x[n + 1 - r] - x[n - r];
                    set_min(early[l][r + 1][j + (s <= t[n - 1 - r])][1], s);
                }
            }
        }
    }

    int ans = 0;
    for (int l = 0; l <= n; ++l) {
        int r = n - l;
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j < 2; ++j) {
                if (early[l][r][i][j] <= T) {
                    ans = max(ans, i);
                }
            }
        }
    }

    cout << ans << "\n";
}

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