Submission #481358

#	Time	Username	Problem	Language	Result	Execution time	Memory
481358		Rainbowbunny	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	262 ms	132568 KiB

ho_t3

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

const int MAXN = 205;
const int INF = 2e9 + 5;

int n, l, ans;
long long X[MAXN], t[MAXN];
long long dp[MAXN][MAXN][MAXN][2];

long long f(long long x)
{
    return min(x, l - x);
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> l;
    for(int i = 1; i <= n; i++)
    {
        cin >> X[i];
    }
    for(int i = 1; i <= n; i++)
    {
        cin >> t[i];
    }
    for(int i = 0; i <= n; i++)
    {
        for(int j = 0; j <= n; j++)
        {
            for(int k = 0; k <= n; k++)
            {
                for(int h = 0; h < 2; h++)
                {
                    dp[i][j][k][h] = INF;
                }
            }
        }
    }
    dp[0][0][0][0] = 0;
    queue <tuple <long long, int, int, int, int> > pq;
    pq.push(make_tuple(0, 0, 0, 0, 0));
    while(pq.empty() == false)
    {
        int d, l, r, k, h;
        tie(d, l, r, k, h) = pq.front();
        pq.pop();
        d = -d;
        ans = max(ans, k);
        if(d == dp[l][r][k][h])
        {
            int prv = l - 1;
            if(prv == -1)
            {
                prv = n;
            }
            
            if(prv != r)
            {
                long long dist = d + f(abs(X[prv] - (h ? X[r] : X[l])));
                if(dist <= t[prv] and prv != 0)
                {
                    if(dp[prv][r][k + 1][0] > dist)
                    {
                        dp[prv][r][k + 1][0] = dist;
                        pq.push(make_tuple(-dist, prv, r, k + 1, 0));
                    }
                }
                else
                {
                    if(dp[prv][r][k][0] > dist)
                    {
                        dp[prv][r][k][0] = dist;
                        pq.push(make_tuple(-dist, prv, r, k, 0));
                    }
                }
            }
            int nxt = r + 1;
            if(nxt != l)
            {
                long long dist = d + f(abs(X[nxt] - (h ? X[r] : X[l])));
                if(dist <= t[nxt] and nxt != 0)
                {
                    if(dp[l][nxt][k + 1][1] > dist)
                    {
                        dp[l][nxt][k + 1][1] = dist;
                        pq.push(make_tuple(-dist, l, nxt, k + 1, 1));
                    }
                }
                else
                {
                    if(dp[l][nxt][k][1] > dist)
                    {
                        dp[l][nxt][k][1] = dist;
                        pq.push(make_tuple(-dist, l, nxt, k, 1));
                    }
                }
            }
        }
    }
    cout << ans << '\n';
}

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