Submission #554822

#	Time	Username	Problem	Language	Result	Execution time	Memory
554822		andrei_boaca	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	55 ms	66728 KiB

ho_t3

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll INF=1e14;
ll n,l,x[205],t[205],dist[205][205],dp[205][205][205][2],ans;
int main()
{
    ios_base::sync_with_stdio(false);
    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<=n+1;i++)
        for(int j=0;j<=n+1;j++)
        {
            dist[i][j]=abs(x[i]-x[j]);
            dist[i][j]=min(dist[i][j],l-dist[i][j]);
        }
    for(int i=0;i<=n;i++)
        for(int j=0;j+i<=n;j++)
        {
            for(int take=0;take<=n;take++)
            {
                dp[i][j][take][0]=dp[i][j][take][1]=INF;
                if(i==0&&j==0&&take==0)
                {
                    dp[i][j][take][0]=dp[i][j][take][1]=0;
                    continue;
                }
                if(i-1>=0)
                {
                    ll val=INF;
                    val=min(val,dp[i-1][j][take][0]+dist[i][i-1]);
                    val=min(val,dp[i-1][j][take][1]+dist[i][n-j+1]);
                    if(take>0)
                    {
                        if(dp[i-1][j][take-1][0]+dist[i][i-1]<=t[i])
                            val=min(val,dp[i-1][j][take-1][0]+dist[i][i-1]);
                        if(dp[i-1][j][take-1][1]+dist[i][n-j+1]<=t[i])
                            val=min(val,dp[i-1][j][take-1][1]+dist[i][n-j+1]);
                    }
                    dp[i][j][take][0]=val;
                }
                if(j-1>=0)
                {
                    ll val=INF;
                    val=min(val,dp[i][j-1][take][0]+dist[i][n-j+1]);
                    val=min(val,dp[i][j-1][take][1]+dist[n-(j-1)+1][n-j+1]);
                    if(take>0)
                    {
                        if(dp[i][j-1][take-1][0]+dist[i][n-j+1]<=t[n-j+1])
                            val=min(val,dp[i][j-1][take-1][0]+dist[i][n-j+1]);
                        if(dp[i][j-1][take-1][1]+dist[n-(j-1)+1][n-j+1]<=t[n-j+1])
                            val=min(val,dp[i][j-1][take-1][1]+dist[n-(j-1)+1][n-j+1]);
                    }
                    dp[i][j][take][1]=val;
                }
                if(min(dp[i][j][take][1],dp[i][j][take][0])<INF)
                    ans=max(ans,1LL*take);
            }
        }
    cout<<ans;
    return 0;
}

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