Submission #1326238

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326238		sh_qaxxorov_571	Collecting Stamps 3 (JOI20_ho_t3)	C++20	0 / 100	1 ms	568 KiB

ho_t3

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const long long INF = 1e18;

// DP holati: dp[i][j][k][pos]
// i - soat mili bo'yicha olingan shtamplar soni (o'ngga)
// j - soat miliga qarshi olingan shtamplar soni (chapga)
// k - jami to'plangan shtamplar soni
// pos - hozirgi turgan joy (0: o'ng tomondagi oxirgi nuqtada, 1: chap tomondagi oxirgi nuqtada)
long long dp[205][205][205][2];

int main() {
    int N;
    long long L;
    cin >> N >> L;

    vector<long long> X(N + 2), T(N + 2);
    for (int i = 1; i <= N; i++) cin >> X[i];
    for (int i = 1; i <= N; i++) cin >> T[i];

    // Chegaraviy qiymatlarni o'rnatamiz (0 - boshlang'ich nuqta)
    X[0] = 0; X[N + 1] = L;
    
    // DPni cheksizlik bilan to'ldiramiz
    for (int i = 0; i <= N; i++)
        for (int j = 0; i + j <= N; j++)
            for (int k = 0; k <= N; k++)
                dp[i][j][k][0] = dp[i][j][k][1] = INF;

    dp[0][0][0][0] = dp[0][0][0][1] = 0;

    for (int i = 0; i <= N; i++) {
        for (int j = 0; i + j <= N; j++) {
            for (int k = 0; k <= i + j; k++) {
                if (dp[i][j][k][0] == INF && dp[i][j][k][1] == INF) continue;

                // Hozirgi koordinatalar
                long long curX_R = X[i];
                long long curX_L = (j == 0) ? 0 : X[N - j + 1];

                // 1. O'ngdan o'ngga o'tish (i -> i+1)
                if (i + j < N) {
                    long long nextX = X[i + 1];
                    // Holat 0 dan (o'ngdan) o'ngga
                    long long time0 = dp[i][j][k][0] + (nextX - curX_R);
                    int nextK = k + (time0 <= T[i + 1] ? 1 : 0);
                    dp[i + 1][j][nextK][0] = min(dp[i + 1][j][nextK][0], time0);

                    // Holat 1 dan (chapdan) o'ngga
                    long long time1 = dp[i][j][k][1] + (curX_L == 0 ? nextX : (L - curX_L + nextX));
                    nextK = k + (time1 <= T[i + 1] ? 1 : 0);
                    dp[i + 1][j][nextK][0] = min(dp[i + 1][j][nextK][0], time1);
                }

                // 2. Chapga o'tish (j -> j+1)
                if (i + j < N) {
                    long long nextX = X[N - j];
                    // Holat 0 dan (o'ngdan) chapga
                    long long time0 = dp[i][j][k][0] + (curX_R == 0 ? (L - nextX) : (curX_R + L - nextX));
                    int nextK = k + (time0 <= T[N - j] ? 1 : 0);
                    dp[i][j + 1][nextK][1] = min(dp[i][j + 1][nextK][1], time0);

                    // Holat 1 dan (chapdan) chapga
                    long long time1 = dp[i][j][k][1] + (curX_L - nextX);
                    if (j == 0) time1 = L - nextX; // Boshlang'ich holatdan chapga
                    nextK = k + (time1 <= T[N - j] ? 1 : 0);
                    dp[i][j + 1][nextK][1] = min(dp[i][j + 1][nextK][1], time1);
                }
            }
        }
    }

    // Maksimal k ni topamiz
    int ans = 0;
    for (int i = 0; i <= N; i++)
        for (int j = 0; i + j <= N; j++)
            for (int k = 0; k <= N; k++)
                if (dp[i][j][k][0] != INF || dp[i][j][k][1] != INF)
                    ans = max(ans, k);

    cout << ans << endl;

    return 0;
}

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