Submission #481341

#	Time	Username	Problem	Language	Result	Execution time	Memory
481341		Rainbowbunny	Collecting Stamps 3 (JOI20_ho_t3)	C++17	0 / 100	1 ms	332 KiB

ho_t3

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

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

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

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

int 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++)
            {
                dp[i][j][k] = INF;
            }
        }
    }
    dp[0][0][0] = 0;
    priority_queue <tuple <int, int, int, int> > pq;
    pq.push(make_tuple(0, 0, 0, 0));
    while(pq.empty() == false)
    {
        int d, l, r, k;
        tie(d, l, r, k) = pq.top();
        ans = max(ans, k);
        pq.pop();
        if(d == dp[l][r][k])
        {
            if(l > r)
            {
                int prv = l - 1;
                if(prv == -1)
                {
                    prv = n;
                }
                if(prv != r)
                {
                    int dist = dp[l][r][k] + f(abs(X[prv] - X[l]));
                    if(dist <= t[prv] and prv != 0)
                    {
                        if(dp[prv][r][k + 1] > dist)
                        {
                            dp[prv][r][k + 1] = dist;
                            pq.push(make_tuple(dist, prv, r, k + 1));
                        } 
                    }
                    else
                    {
                        if(dp[prv][r][k] > dist)
                        {
                            dp[prv][r][k] = dist;
                            pq.push(make_tuple(dist, prv, r, k));
                        }
                    }
                }
                int nxt = r + 1;
                if(nxt == n + 1)
                {
                    nxt = 0;
                }
                if(nxt != l)
                {
                    int dist = dp[l][r][k] + f(abs(X[l] - X[nxt]));
                    if(dist <= t[nxt] and nxt != 0)
                    {
                        if(dp[nxt][l][k + 1] > dist)
                        {
                            dp[nxt][l][k + 1] = dist;
                            pq.push(make_tuple(dist, nxt, l, k + 1));
                        }
                    }
                    else
                    {
                        if(dp[nxt][l][k] > dist)
                        {
                            dp[nxt][l][k] = dist;
                            pq.push(make_tuple(dist, nxt, l, k));
                        }
                    }
                }
            }
            else
            {
                int prv = r - 1;
                if(prv == -1)
                {
                    prv = n;
                }
                if(prv != l)
                {
                    int dist = dp[l][r][k] + f(abs(X[prv] - X[l]));
                    if(dist <= t[prv] and prv != 0)
                    {
                        if(dp[prv][l][k + 1] > dist)
                        {
                            dp[prv][l][k + 1] = dist;
                            pq.push(make_tuple(dist, prv, l, k + 1));
                        } 
                    }
                    else
                    {
                        if(dp[prv][l][k] > dist)
                        {
                            dp[prv][l][k] = dist;
                            pq.push(make_tuple(dist, prv, l, k));
                        }
                    }
                }
                int nxt = l + 1;
                if(nxt == n + 1)
                {
                    nxt = 0;
                }
                if(nxt != r)
                {
                    
                    int dist = dp[l][r][k] + f(abs(X[l] - X[nxt]));
                    if(dist <= t[nxt] and nxt != 0)
                    {
                        if(dp[nxt][r][k + 1] > dist)
                        {
                            dp[nxt][r][k + 1] = dist;
                            pq.push(make_tuple(dist, nxt, r, k + 1));
                        }
                    }
                    else
                    {
                        if(dp[nxt][r][k] > dist)
                        {
                            dp[nxt][r][k] = dist;
                            pq.push(make_tuple(dist, nxt, r, k));
                        }
                    }
                }
            }
        }
    }
    cout << ans << '\n';
}

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