Submission #202628

#	Time	Username	Problem	Language	Result	Execution time	Memory
202628		SamAnd	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	150 ms	129576 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;
const int N = 202;
const long long INF = 1000000009000000009;

int n, L;
int x[N], t[N];

int ans;
long long dp[N][N][2][N];

int dist1(int x, int y)
{
    if (y <= x)
        return (x - y);
    return L - (y - x);
}

int dist2(int x, int y)
{
    if (y >= x)
        return (y - x);
    return L - (x - y);
}

int main()
{
    //freopen("input.txt", "r", stdin);
    scanf("%d%d", &n, &L);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &x[i]);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &t[i]);
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            for (int z = 0; z < 2; ++z)
            {
                for (int k = 0; k < N; ++k)
                {
                    dp[i][j][z][k] = INF;
                }
            }
        }
    }
    dp[0][0][0][0] = dp[0][0][1][0] = 0;
    for (int i = 0; i <= n; ++i)
    {
        for (int j = 0; j <= n; ++j)
        {
            for (int z = 0; z < 2; ++z)
            {
                for (int k = 0; k <= n; ++k)
                {
                    if (dp[i][j][z][k] == INF)
                        continue;
                    ans = max(ans, k);
                    if (z == 0)
                    {
                        if (i + 1 + j <= n)
                        {
                            int v = (n - i + 1) % (n + 1);
                            int u = (n - (i + 1) + 1) % (n + 1);
                            if (dp[i][j][z][k] + dist1(x[v], x[u]) <= t[u])
                                dp[i + 1][j][z][k + 1] = min(dp[i + 1][j][z][k + 1], dp[i][j][z][k] + dist1(x[v], x[u]));
                            else
                                dp[i + 1][j][z][k] = min(dp[i + 1][j][z][k], dp[i][j][z][k] + dist1(x[v], x[u]));
                        }
                        if (i + j + 1 <= n)
                        {
                            int v = (n - i + 1) % (n + 1);
                            int u = j + 1;
                            if (dp[i][j][z][k] + dist2(x[v], x[u]) <= t[u])
                                dp[i][j + 1][(z ^ 1)][k + 1] = min(dp[i][j + 1][(z ^ 1)][k + 1], dp[i][j][z][k] + dist2(x[v], x[u]));
                            else
                                dp[i][j + 1][(z ^ 1)][k] = min(dp[i][j + 1][(z ^ 1)][k], dp[i][j][z][k] + dist2(x[v], x[u]));
                        }
                    }
                    else
                    {
                        if (i + j + 1 <= n)
                        {
                            int v = j;
                            int u = j + 1;
                            if (dp[i][j][z][k] + dist2(x[v], x[u]) <= t[u])
                                dp[i][j + 1][z][k + 1] = min(dp[i][j + 1][z][k + 1], dp[i][j][z][k] + dist2(x[v], x[u]));
                            else
                                dp[i][j + 1][z][k] = min(dp[i][j + 1][z][k], dp[i][j][z][k] + dist2(x[v], x[u]));
                        }
                        if (i + 1 + j <= n)
                        {
                            int v = j;
                            int u = (n - (i + 1) + 1) % (n + 1);
                            if (dp[i][j][z][k] + dist1(x[v], x[u]) <= t[u])
                                dp[i + 1][j][(z ^ 1)][k + 1] = min(dp[i + 1][j][(z ^ 1)][k + 1], dp[i][j][z][k] + dist1(x[v], x[u]));
                            else
                                dp[i + 1][j][(z ^ 1)][k] = min(dp[i + 1][j][(z ^ 1)][k], dp[i][j][z][k] + dist1(x[v], x[u]));
                        }
                    }
                }
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

Compilation message (stderr)

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &L);
     ~~~~~^~~~~~~~~~~~~~~~
ho_t3.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x[i]);
         ~~~~~^~~~~~~~~~~~~
ho_t3.cpp:33:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &t[i]);
         ~~~~~^~~~~~~~~~~~~

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