Submission #1180555

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180555		MongHwa	Collecting Stamps 3 (JOI20_ho_t3)	C++20	100 / 100	152 ms	141924 KiB

ho_t3

#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#include <iostream>
#include <queue>
#include <tuple>
using namespace std;

#define ll long long
#define INF 1e17

int ans;
int n, L;
ll x[205], t[205];
ll dp[2][205][205][205];
bool status[2][205][205][205];
queue<tuple<int, int, int, int>> q;

int main()
{
    ios::sync_with_stdio(0);
    cin.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 < 2; i++)
        for(int ii = 0; ii <= n; ii++)
            for(int iii = 0; iii <= n; iii++)
                for(int iv = 0; iv <= n; iv++)
                    dp[i][ii][iii][iv] = INF;
    
    if(L-x[n] <= t[n])
    {
        dp[0][n-1][1][1] = L-x[n];
        status[0][n-1][1][1] = 1;
        q.push({0, n-1, 1, 1});
    }
    else
    {
        dp[0][n-1][1][0] = L-x[n];
        status[0][n-1][1][0] = 1;
        q.push({0, n-1, 1, 0});
    }

    if(x[1] <= t[1])
    {
        dp[1][n][2][1] = x[1];
        status[1][n][2][1] = 1;
        q.push({1, n, 2, 1});
    }
    else
    {
        dp[1][n][2][0] = x[1];
        status[1][n][2][0] = 1;
        q.push({1, n, 2, 0});
    }

    while(1)
    {
        bool ok = 0;
        int sz = (int)q.size();
        while(sz--)
        {
            ok = 1;
            int type, l, r, cnt;
            tie(type, l, r, cnt) = q.front(); q.pop();

            ans = max(ans, cnt);
            if(l < r)
                continue;

            int cur = (type ? r-1 : l+1);
            int pp = (dp[type][l][r][cnt]+(x[cur]-x[l]+L)%L <= t[l]);
            dp[0][l-1][r][cnt+pp] = min(dp[0][l-1][r][cnt+pp], dp[type][l][r][cnt]+(x[cur]-x[l]+L)%L);
            if(!status[0][l-1][r][cnt+pp])
            {
                status[0][l-1][r][cnt+pp] = 1;
                q.push({0, l-1, r, cnt+pp});
            }

            pp = (dp[type][l][r][cnt]+(x[r]-x[cur]+L)%L <= t[r]);
            dp[1][l][r+1][cnt+pp] = min(dp[1][l][r+1][cnt+pp], dp[type][l][r][cnt]+(x[r]-x[cur]+L)%L);
            if(!status[1][l][r+1][cnt+pp])
            {
                status[1][l][r+1][cnt+pp] = 1;
                q.push({1, l, r+1, cnt+pp});
            }
        }

        if(!ok)
            break;
    }

    cout << ans << '\n';
}

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