oj.uz

Submission #540937

# Submission time Handle Problem Language Result Execution time Memory
540937 2022-03-22T03:04:39 Z LittleCube Collecting Stamps 3 (JOI20_ho_t3) C++14
0 / 100
 1 ms 724 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

ll N, L, dp[405][405][205][2], dis[405][405], ans;
pll a[405];

signed main()
{
    cin >> N >> L;
    for (int i = 1; i <= N; i++)
        cin >> a[i].F;
    for (int i = 1; i <= N; i++)
        cin >> a[i].S;
    for (int i = 1; i <= N; i++)
    {
        a[i + N] = a[i];
        a[i].F -= L;
    }
    N *= 2;
    for (int i = 1; i <= N; i++)
        for (int j = i + 1; j <= N; j++)
            dis[i][j] = dis[i][j - 1] + a[j].F - a[j - 1].F;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            for (int k = 0; k <= N / 2; k++)
                dp[i][j][k][0] = dp[i][j][k][1] = 2e17;

    for (int i = 1; i <= N; i++)
        dp[i][i][abs(a[i].S) >= abs(a[i].F)][0] = dp[i][i][abs(a[i].S) >= abs(a[i].F)][1] = abs(a[i].F);

    for (int k = 0; k <= N / 2; k++)
        for (int i = 1; i <= N; i++)
            for (int j = i; j <= min(i + N / 2, N); j++)
                if (dp[i][j][k][0] <= 1e17 || dp[i][j][k][1] <= 1e17)
                {
                    //printf("%d %d %d %d = %lld\n", i, j, k, 0, dp[i][j][k][0]);
                    //printf("%d %d %d %d = %lld\n", i, j, k, 1, dp[i][j][k][1]);
                    ans = max(ans, (ll)k);
                    int dk = (dp[i][j][k][0] + dis[i - 1][i] <= a[i - 1].S);
                    dp[i - 1][j][k + dk][0] = min(dp[i - 1][j][k + dk][0], dp[i][j][k][0] + dis[i - 1][i]);

                    dk = (dp[i][j][k][0] + dis[i][j + 1] <= a[j + 1].S);
                    dp[i][j + 1][k + dk][1] = min(dp[i][j + 1][k + dk][1], dp[i][j][k][0] + dis[i][j + 1]);

                    dk = (dp[i][j][k][1] + dis[i - 1][j] <= a[i - 1].S);
                    dp[i - 1][j][k + dk][0] = min(dp[i - 1][j][k + dk][0], dp[i][j][k][1] + dis[i - 1][j]);

                    dk = (dp[i][j][k][1] + dis[j][j + 1] <= a[j + 1].S);
                    dp[i][j + 1][k + dk][1] = min(dp[i][j + 1][k + dk][1], dp[i][j][k][1] + dis[j][j + 1]);
                }
    cout << ans << '\n';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Incorrect 1 ms 724 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Incorrect 1 ms 724 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Incorrect 1 ms 724 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Incorrect 1 ms 724 KB Output isn't correct
3 Halted 0 ms 0 KB -