Submission #556883

#	Time	Username	Problem	Language	Result	Execution time	Memory
556883		alextodoran	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	77 ms	64512 KiB

ho_t3

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 200;

const int INF = INT_MAX / 2;
const int LEFT = 0;
const int RIGHT = 1;

int N, L;
int X[N_MAX + 2];
int T[N_MAX + 2];

int minT[N_MAX + 2][N_MAX + 2][N_MAX + 2][2];
// minT[k][l][r][last] = Minimum time required to get k stamps,
// visiting the first l stands and the last r stands,
// the final position being at l or at r depending on last

void update (int &x, const int &y) {
    if (y < x) {
        x = y;
    }
}

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

    cin >> N >> L;
    for (int i = 1; i <= N; i++) {
        cin >> X[i];
    }
    for (int i = 1; i <= N; i++) {
        cin >> T[i];
    }
    X[0] = 0;
    X[N + 1] = L;

    for (int k = 0; k <= N; k++) {
        for (int l = 0; l <= N; l++) {
            for (int r = 0; r <= N; r++) {
                minT[k][l][r][LEFT] = INF;
                minT[k][l][r][RIGHT] = INF;
            }
        }
    }
    minT[0][0][0][LEFT] = 0;
    minT[0][0][0][RIGHT] = 0;
    for (int k = 0; k <= N; k++) {
        for (int l = 0; l <= N; l++) {
            for (int r = 0; l + r < N; r++) {
                int swpSide = X[l] + (L - X[(N + 1) - r]);
                update(minT[k][l][r][LEFT], minT[k][l][r][RIGHT] + swpSide);
                update(minT[k][l][r][RIGHT], minT[k][l][r][LEFT] + swpSide);
                int newTLeft = minT[k][l][r][LEFT] + (X[l + 1] - X[l]);
                int newTRight = minT[k][l][r][RIGHT] + (X[(N + 1) - r] - X[(N + 1) - (r + 1)]);
                update(minT[k + (newTLeft <= T[l + 1])][l + 1][r][LEFT], newTLeft);
                update(minT[k + (newTRight <= T[(N + 1) - (r + 1)])][l][r + 1][RIGHT], newTRight);
            }
        }
    }

    int answer = 0;
    for (int k = 0; k <= N; k++) {
        for (int l = 0; l <= N; l++) {
            for (int r = (l == 0); l + r <= N; r++) {
                if (minT[k][l][r][LEFT] != INF || minT[k][l][r][RIGHT] != INF) {
                    answer = k;
                }
            }
        }
    }
    cout << answer << "\n";

    return 0;
}

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