Submission #896818

#	Time	Username	Problem	Language	Result	Execution time	Memory
896818		ace5	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	43 ms	134000 KiB

ho_t3

#include <bits/stdc++.h>

using namespace std;

#define int int64_t

const int INF = 1e18;
const int maxn = 205;

int dp[maxn][maxn][maxn][2] = {0};
int a[maxn] = {0};
int t[maxn] = {0};

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,L;
    cin >> n >> L;
    for(int j =1;j <= n;++j)
    {
        cin >> a[j];
    }
    a[n+1] = L;
    for(int j =1;j <= n;++j)
    {
        cin >> t[j];
    }
    for(int i = 0;i <= n;++i)
    {
        for(int j = 0;j <= n;++j)
        {
            for(int k = 0;k <= n;++k)
            {
                for(int l = 0;l < 2;++l)
                    dp[i][j][k][l] = INF;
            }

        }
    }
    int ans = 0;
    for(int lx = 0;lx <= n;++lx)
    {
        for(int rx = 0;lx+rx <= n;++rx)
        {
            for(int k = 0;k <= lx+rx;++k)
            {
                for(int l = 0;l < 2;++l)
                {
                    if(lx == 0 && rx == 0)
                        dp[lx][rx][k][l] = 0;
                    else
                    {
                        if(l == 0)
                        {
                            if(lx != 0)
                            {
                                dp[lx][rx][k][l] = min(dp[lx][rx][k][l],dp[lx-1][rx][k][0] + a[lx]-a[lx-1]);
                                dp[lx][rx][k][l] = min(dp[lx][rx][k][l],dp[lx-1][rx][k][1] + L-a[n-rx+1]+a[lx]);
                                if(k != 0 && dp[lx-1][rx][k-1][0] + a[lx]-a[lx-1] <= t[lx])
                                    dp[lx][rx][k][l] = min(dp[lx][rx][k][l],dp[lx-1][rx][k-1][0] + a[lx]-a[lx-1]);
                                if(k != 0 && dp[lx-1][rx][k-1][1] + L-a[n-rx+1]+a[lx] <= t[lx])
                                    dp[lx][rx][k][l] = min(dp[lx][rx][k][l],dp[lx-1][rx][k-1][1] + L-a[n-rx+1]+a[lx]);
                            }
                        }
                        else
                        {
                            if(rx != 0)
                            {
                                dp[lx][rx][k][l] = min(dp[lx][rx][k][l],dp[lx][rx-1][k][0] + a[lx] + L - a[n-rx+1]);
                                dp[lx][rx][k][l] = min(dp[lx][rx][k][l],dp[lx][rx-1][k][1] + a[n-rx+2]-a[n-rx+1]);
                                if(k != 0 && dp[lx][rx-1][k-1][0] + a[lx] + L - a[n-rx+1] <= t[n-rx+1])
                                    dp[lx][rx][k][l] = min(dp[lx][rx][k][l],dp[lx][rx-1][k-1][0] + a[lx] + L - a[n-rx+1]);
                                if(k != 0 && dp[lx][rx-1][k-1][1] + a[n-rx+2]-a[n-rx+1] <= t[n-rx+1])
                                    dp[lx][rx][k][l] = min(dp[lx][rx][k][l],dp[lx][rx-1][k-1][1] + a[n-rx+2]-a[n-rx+1]);
                            }
                        }
                    }
                    if(dp[lx][rx][k][l] != INF)
                    {
                       // cout << lx << ' ' << rx << ' ' << k << ' ' << l << ' ' << dp[lx][rx][k][l] << "\n";
                        ans = max(ans,k);
                    }
                }
            }
        }
    }

    cout << ans;
    return 0;
}

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