Submission #371174

#	Time	Username	Problem	Language	Result	Execution time	Memory
371174		Fysty	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	134 ms	131436 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep1(i,n) for(ll i=1;i<=n;i++)
#define F first
#define S second
#define pb push_back
const ll INF=1e18;
ll dp[205][205][205][2];
ll a[205],t[205];
void upd(ll &x,ll &y)
{
    if(x>y) x=y;
}
int main()
{
    ll n,L,ans=0;
    cin>>n>>L;
    rep1(i,n) cin>>a[i];
    rep1(i,n) cin>>t[i];
    rep(i,n+1) rep(j,n+2) rep(k,n+1) rep(l,2) dp[i][j][k][l]=INF+1;
    dp[0][n+1][0][0]=0;
    rep(i,n+1)
    {
        for(int j=n+1;j>=i+1;j--)
        {
            rep(k,i+n+1-j+1)
            {
                rep(l,2)
                {
                    if(dp[i][j][k][l]>INF) continue;
                    ll cur=dp[i][j][k][l];
                    ans=max(ans,k);
                    if(l==0)
                    {
                        if(i<n)
                        {
                            ll tmp=cur+a[i+1]-a[i];
                            upd(dp[i+1][j][k+(tmp<=t[i+1])][0],tmp);
                        }
                        if(j>1)
                        {
                            ll tmp=cur+a[i]+L-a[j-1];
                            upd(dp[i][j-1][k+(tmp<=t[j-1])][1],tmp);
                        }
                    }
                    else
                    {
                        if(i<n)
                        {
                            ll tmp=cur+L-a[j]+a[i+1];
                            upd(dp[i+1][j][k+(tmp<=t[i+1])][0],tmp);
                        }
                        if(j>1)
                        {
                            ll tmp=cur+a[j]-a[j-1];
                            upd(dp[i][j-1][k+(tmp<=t[j-1])][1],tmp);
                        }
                    }
                }
            }
        }
    }
    cout<<ans;
}

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