Submission #211267

#	Time	Username	Problem	Language	Result	Execution time	Memory
211267		DS007	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	287 ms	144828 KiB

ho_t3

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

const int N = 202;
int n, l;
int x[N], t[N];
int dp[N][N][N][2];
bool seen[N][N][N][2];

int calc(int i, int j, int k, int s) {
    if (seen[i][j][k][s])
        return dp[i][j][k][s];

    seen[i][j][k][s] = true;
    int &val = dp[i][j][k][s];

    if (i + j < k || (i == 0 && s == 0) || (j == 0 && s == 1) || i + j > n)
        return val = 1e11;

    if (k == 0) {
        if (s == 0)
            return val = x[i];
        else
            return val = l - x[n - j + 1];
    }

    if (j == 0) {
        int temp = calc(i - 1, j, k - 1, s);
        if (temp + x[i] - x[i - 1] <= t[i])
            val = min(val, temp + x[i] - x[i - 1]);
        return val = min(val, calc(i - 1, j, k, s) + x[i] - x[i - 1]);
    }

    if (i == 0) {
        int temp = calc(i, j - 1, k - 1, s);
        if (temp + abs(x[n - j + 2] - x[n - j + 1]) <= t[n - j + 1])
            val = min(val, temp + abs(x[n - j + 2] - x[n - j + 1]));
        return val = min(val, calc(i, j - 1, k, s) + abs(x[n - j + 2] - x[n - j + 1]));
    }

    if (s == 0) {
        int temp = calc(i - 1, j, k - 1, s);
        if (temp + x[i] - x[i - 1] <= t[i])
            val = min(val, temp + x[i] - x[i - 1]);
        val = min(val, calc(i - 1, j, k, s) + x[i] - x[i - 1]);

        temp = calc(i - 1, j, k - 1, 1);
        if (temp + x[i] + l - x[n - j + 1] <= t[i])
            val = min(val, temp + x[i] + l - x[n - j + 1]);
        return val = min(val, calc(i - 1, j, k, 1) + x[i] + l - x[n - j + 1]);
    }

    if (s == 1) {
        int temp = calc(i, j - 1, k - 1, s);
        if (temp + abs(x[n - j + 2] - x[n - j + 1]) <= t[n - j + 1])
            val = min(val, temp + abs(x[n - j + 2] - x[n - j + 1]));
        val = min(val, calc(i, j - 1, k, s) + abs(x[n - j + 2] - x[n - j + 1]));

        temp = calc(i, j - 1, k - 1, 0);
        if (temp + x[i] + l - x[n - j + 1] <= t[n - j + 1])
            val = min(val, temp + x[i] + l - x[n - j + 1]);
        return val = min(val, calc(i, j - 1, k, 0) + x[i] + l - x[n - j + 1]);
    }
}

void solveTestCase() {
    cin >> n >> l;
    for (int i = 1; i <= n; i++) cin >> x[i];
    for (int i = 1; i <= n; i++) cin >> t[i];
    x[n + 1] = l;

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            for (int k = 0; k <= n; k++)
                dp[i][j][k][0] = dp[i][j][k][1] = 1e11;
        }
    }

    dp[0][0][0][0] = dp[0][0][0][1] = 0;
    seen[0][0][0][0] = seen[0][0][0][1] = true;

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            for (int k = 0; k <= n; k++)
                dp[i][j][k][0] = calc(i, j, k, 0), dp[i][j][k][1] = calc(i, j, k, 1);
        }
    }

    int ans = 0;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            for (int k = 0; k <= n; k++) {
                int a1 = dp[i][j][k][0], a2 = dp[i][j][k][1];
                if (dp[i][j][k][0] < 1e11)
                    ans = max(ans, k);
                if (dp[i][j][k][1] < 1e11)
                    ans = max(ans, k);
            }
        }
    }

    cout << ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int test = 1;
    //cin >> test;
    while (test--)
        solveTestCase();
}

Compilation message (stderr)

ho_t3.cpp: In function 'void solveTestCase()':
ho_t3.cpp:94:21: warning: unused variable 'a1' [-Wunused-variable]
                 int a1 = dp[i][j][k][0], a2 = dp[i][j][k][1];
                     ^~
ho_t3.cpp:94:42: warning: unused variable 'a2' [-Wunused-variable]
                 int a1 = dp[i][j][k][0], a2 = dp[i][j][k][1];
                                          ^~
ho_t3.cpp: In function 'long long int calc(long long int, long long int, long long int, long long int)':
ho_t3.cpp:65:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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