Submission #365236

#	Time	Username	Problem	Language	Result	Execution time	Memory
365236		Dymo	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	125 ms	134124 KiB

ho_t3

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

#define ll long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
//#define endl "\n"
const ll maxn =2e2+10;
const ll mod=1e9+7;
const ll base=1e18;

ll dp[maxn][maxn][maxn][2];
ll x[maxn];
ll t[maxn];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("t.inp","r"))
    {
        freopen("test.inp","r",stdin);
        freopen("test.out","w",stdout);
    }
    ll n,l ;
    cin>>n>>l  ;
    x[0]=0;

    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++)
            {
                for (int t=0; t<=1; t++)
                    dp[i][j][k][t]=base;
            }
        }
    }
    dp[0][0][0][0]=0;
    dp[0][0][0][1]=0;
    for (int len=1; len<=n; len++)
    {
        for (int j=0; j-len<0; j++)
        {
            ll nxt=j-len+1;
            if (nxt<0)
                nxt+=(n+1);

            for (int cnt=0; cnt<=n; cnt++)
            {
                // dp[nxt][j][cnt][0]
                ll kc=abs(x[nxt]-x[(nxt-1+(n+1))%(n+1)]);
                if (nxt==0)
                {
                    kc=l-x[n];
                }
                if (dp[nxt][j][cnt][0]+kc<=t[(nxt-1+(n+1))%(n+1)])
                {
                    dp[(nxt-1+(n+1))%(n+1)][j][cnt+1][0]=min(dp[(nxt-1+(n+1))%(n+1)][j][cnt+1][0],dp[nxt][j][cnt][0]+kc);
                }
                else
                {
                    dp[(nxt-1+(n+1))%(n+1)][j][cnt][0]=min(dp[(nxt-1+(n+1))%(n+1)][j][cnt][0],dp[nxt][j][cnt][0]+kc);
                }
                kc=abs(x[nxt]-x[j+1]);
                if (nxt!=0)
                {
                    kc=l-x[nxt]+x[j+1];
                }
                if (dp[nxt][j][cnt][0]+kc<=t[j+1])
                {
                    dp[nxt][j+1][cnt+1][1]=min(dp[nxt][j+1][cnt+1][1],dp[nxt][j][cnt][0]+kc);
                }
                else
                {
                    dp[nxt][j+1][cnt][1]=min(dp[nxt][j+1][cnt][1],dp[nxt][j][cnt][0]+kc);
                }
                // dp[nxt][j][cnt][1]
                kc=min(abs(x[j]-x[(nxt-1+(n+1))%(n+1)]),x[j]+l-x[(nxt-1+(n+1))%(n+1)]);
                if (nxt==0)
                {
                    kc=l-x[n]+x[j];
                }
                if (dp[nxt][j][cnt][1]+kc<=t[(nxt-1+(n+1))%(n+1)])
                {
                    dp[(nxt-1+(n+1))%(n+1)][j][cnt+1][0]=min(dp[(nxt-1+(n+1))%(n+1)][j][cnt+1][0],dp[nxt][j][cnt][1]+kc);
                }
                else
                {
                    dp[(nxt-1+(n+1))%(n+1)][j][cnt][0]=min(dp[(nxt-1+(n+1))%(n+1)][j][cnt][0],dp[nxt][j][cnt][1]+kc);
                }
                kc=abs(x[j]-x[j+1]);
                if (dp[nxt][j][cnt][1]+kc<=t[j+1])
                {
                    dp[nxt][j+1][cnt+1][1]=min(dp[nxt][j+1][cnt+1][1],dp[nxt][j][cnt][1]+kc);
                }
                else
                {
                    dp[nxt][j+1][cnt][1]=min(dp[nxt][j+1][cnt][1],dp[nxt][j][cnt][1]+kc);
                }

            }
        }
    }
   // cout <<dp[6][0][1][0]<<endl;
   // cout <<dp[5][0][2][0]<<endl;
   // cout <<dp[5][1][3][1]<<endl;
    ll ans=0;
    for (int i=0; i<=n; i++)
    {
        for (int j=0; j<=n; j++)
        {
            for (ll k=0; k<=n; k++)
            {
                for (int t=0; t<=1; t++)
                {
                  if (dp[i][j][k][t]!=base)
                  {
                      ans=max(ans,k);
                  }
                }
            }
        }
    }
    cout <<ans;


}

Compilation message (stderr)

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:25:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   25 |         freopen("test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
ho_t3.cpp:26:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   26 |         freopen("test.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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