Submission #1122790

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122790		LucaIlie	Collecting Stamps 3 (JOI20_ho_t3)	C++20	100 / 100	61 ms	63816 KiB

ho_t3

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 201;
const int MAX_T = 1e9 + 1;
int x[MAX_N], t[MAX_N];
int minTimeL[MAX_N][MAX_N][MAX_N], minTimeR[MAX_N][MAX_N][MAX_N];

int main() {
    int n, l;

    cin >> n >> l;
    x[0] = 0;
    for ( int i = 1; i <= n; i++ )
        cin >> x[i];
    x[n + 1] = l;
    t[0] = -1;
    for ( int i = 1; i <= n; i++ )
        cin >> t[i];
    t[n + 1] = -1;

    for ( int i = 0; i <= n; i++ ) {
        for ( int j = 0; j <= n; j++ ) {
            for ( int k = 0; k <= n; k++ )
                minTimeL[i][j][k] = minTimeR[i][j][k] = MAX_T;
        }
    }

    minTimeL[0][0][0] = minTimeR[0][0][0] = 0;

    int maxStamps = 0;
    for ( int i = 0; i <= n; i++ ) {
        for ( int j = 0; i + j <= n; j++ ) {
            for ( int k = n - 1; k >= 0; k-- ) {
                if ( minTimeL[i][j][k] <= t[n + 1 - i] )
                    minTimeL[i][j][k + 1] = min( minTimeL[i][j][k + 1], minTimeL[i][j][k] );
                if ( minTimeR[i][j][k] <= t[j] )
                    minTimeR[i][j][k + 1] = min( minTimeR[i][j][k + 1], minTimeR[i][j][k] );
            }
            for ( int k = 0; k <= n; k++ ) {
                if ( minTimeL[i][j][k] < MAX_T )
                    maxStamps = max( maxStamps, k );
                if ( minTimeR[i][j][k] < MAX_T )
                    maxStamps = max( maxStamps, k );
                minTimeL[i + 1][j][k] = min( minTimeL[i + 1][j][k], minTimeL[i][j][k] + x[n + 1 - i] - x[n - i] );
                minTimeL[i + 1][j][k] = min( minTimeL[i + 1][j][k], minTimeR[i][j][k] + x[j] + l - x[n - i] );
                minTimeR[i][j + 1][k] = min( minTimeR[i][j + 1][k], minTimeL[i][j][k] + l - x[n + 1 - i] + x[j + 1] );
                minTimeR[i][j + 1][k] = min( minTimeR[i][j + 1][k], minTimeR[i][j][k] + x[j + 1] - x[j] );
            }
        }
    }

    cout << maxStamps << "\n";
}

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