Submission #1341623

#TimeUsernameProblemLanguageResultExecution timeMemory
1341623iamhereforfunCollecting Stamps 3 (JOI20_ho_t3)C++20
100 / 100
126 ms135636 KiB
// Starcraft 2 enjoyer //

#include <bits/stdc++.h>

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

#define LSOne(X) ((X) & -(X))

const int N = 2e2 + 5;
const int K = 1e2 + 5;
const int M = 2e5 + 5;
const int LG = 20;
const long long INF = 1e18 + 5;
const int C = 26;
const int B = 1000;
const int MOD = 998244353;

int n, l, a[N], ans;
long long dp[2][N][N][N], t[N], dis[N][N];

inline void solve()
{
    cin >> n >> l;
    memset(dp, -1, sizeof(dp));
    a[0] = 0;
    for (int x = 1; x <= n; x++)
    {
        cin >> a[x];
    }
    t[0] = INF;
    for (int x = 1; x <= n; x++)
    {
        cin >> t[x];
    }
    n++;
    for (int x = 0; x < n; x++)
    {
        for (int y = 0; y < n; y++)
        {
            int z = y;
            while (z != x)
            {
                int nxt = (z + 1) % n;
                dis[x][y] += (a[nxt] - a[z] + l) % l;
                z = nxt;
            }
            dis[x][y] = min(dis[x][y], l - dis[x][y]);
            // cout << dis[x][y] << " " << x << " " << y << "\n";
        }
    }
    dp[0][0][0][0] = 0;
    dp[1][0][0][0] = 0;
    for (int s = 0; s < n - 1; s++)
    {
        for (int r = s; r >= 0; r--)
        {
            int l = (r - s + n) % n;
            for (int z = 0; z < n; z++)
            {
                if (dp[0][l][r][z] != -1) // at l
                {
                    // cout << dp[l][r][z] << "|" << a[l] << " " << a[r] << "|" << z << "\n";
                    int nxt = (l - 1 + n) % n;
                    if (dis[l][nxt] + dp[0][l][r][z] <= t[nxt])
                    {
                        if (dp[0][nxt][r][z + 1] == -1 || dp[0][nxt][r][z + 1] > dis[l][nxt] + dp[0][l][r][z])
                        {
                            dp[0][nxt][r][z + 1] = dis[l][nxt] + dp[0][l][r][z];
                        }
                    }
                    else
                    {
                        if (dp[0][nxt][r][z] == -1 || dp[0][nxt][r][z] > dis[l][nxt] + dp[0][l][r][z])
                        {
                            dp[0][nxt][r][z] = dis[l][nxt] + dp[0][l][r][z];
                        }
                    }
                    nxt = (r + 1 + n) % n;
                    if (dis[l][nxt] + dp[0][l][r][z] <= t[nxt])
                    {
                        // cout << a[nxt] << " " << l << " " << z + 1 << "\n";
                        if (dp[1][l][nxt][z + 1] == -1 || dp[1][l][nxt][z + 1] > dis[l][nxt] + dp[0][l][r][z])
                        {
                            dp[1][l][nxt][z + 1] = dis[l][nxt] + dp[0][l][r][z];
                        }
                    }
                    else
                    {
                        if (dp[1][l][nxt][z] == -1 || dp[1][l][nxt][z] > dis[l][nxt] + dp[0][l][r][z])
                        {
                            dp[1][l][nxt][z] = dis[l][nxt] + dp[0][l][r][z];
                        }
                    }
                }
                if (dp[1][l][r][z] != -1) // at r
                {
                    // cout << dp[l][r][z] << "|" << a[l] << " " << a[r] << "|" << z << "\n";
                    int nxt = (l - 1 + n) % n;
                    if (dis[r][nxt] + dp[1][l][r][z] <= t[nxt])
                    {
                        if (dp[0][nxt][r][z + 1] == -1 || dp[0][nxt][r][z + 1] > dis[r][nxt] + dp[1][l][r][z])
                        {
                            dp[0][nxt][r][z + 1] = dis[r][nxt] + dp[1][l][r][z];
                        }
                    }
                    else
                    {
                        if (dp[0][nxt][r][z] == -1 || dp[0][nxt][r][z] > dis[r][nxt] + dp[1][l][r][z])
                        {
                            dp[0][nxt][r][z] = dis[r][nxt] + dp[1][l][r][z];
                        }
                    }
                    nxt = (r + 1 + n) % n;
                    if (dis[r][nxt] + dp[1][l][r][z] <= t[nxt])
                    {
                        // cout << a[nxt] << " " << l << " " << z + 1 << "\n";
                        if (dp[1][l][nxt][z + 1] == -1 || dp[1][l][nxt][z + 1] > dis[r][nxt] + dp[1][l][r][z])
                        {
                            dp[1][l][nxt][z + 1] = dis[r][nxt] + dp[1][l][r][z];
                        }
                    }
                    else
                    {
                        if (dp[1][l][nxt][z] == -1 || dp[1][l][nxt][z] > dis[r][nxt] + dp[1][l][r][z])
                        {
                            dp[1][l][nxt][z] = dis[r][nxt] + dp[1][l][r][z];
                        }
                    }
                }
            }
        }
    }
    for (int x = 0; x < n; x++)
    {
        for (int y = 0; y < n; y++)
        {
            for (int z = 0; z < n; z++)
            {
                if (dp[0][x][y][z] != -1)
                    ans = max(ans, z);
                if (dp[1][x][y][z] != -1)
                    ans = max(ans, z);
            }
        }
    }
    cout << ans << "\n";
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    for (int x = 1; x <= t; x++)
    {
        solve();
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...