Submission #227177

#	Time	Username	Problem	Language	Result	Execution time	Memory
227177		ho94949	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	104 ms	129528 KiB

ho_t3

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

const int MAXN = 200;
const long long INF = 0x3f3f3f3f'3f3f3f3fLL;

//leftmost: i, rightmost: j, visited: 0, cur: left or right. time
long long dp[MAXN+2][MAXN+2][MAXN+2][2]; 
int N, L;
int X[MAXN+1], T[MAXN+1];
int main()
{
    scanf("%d%d", &N, &L);
    for(int i=1; i<=N; ++i) scanf("%d", X+i);
    for(int i=1; i<=N; ++i) scanf("%d", T+i);
    memset(dp, 0x3f, sizeof dp);
    dp[N+1][0][0][0] = dp[N+1][0][0][1] = 0;

    int ans = 0;
    for(int imj = N; imj>0; --imj)
    {
        for(int i=imj; i<=N+1; ++i)
        {
            int j = i-imj;
            for(int t=0; t<=N-imj+1; ++t)
            {
                long long ptime, d;
                if(i != N+1)
                {
                    ptime = dp[i+1][j][t][0];
                    d = abs(X[i]-X[i+1]); d = min(d, L-d);
                    if(ptime+d<=T[i]) 
                        dp[i][j][t+1][0] = min(dp[i][j][t+1][0], ptime+d);
                    else 
                        dp[i][j][t][0] = min(dp[i][j][t][0], ptime+d);

                    ptime = dp[i+1][j][t][1];
                    d = abs(X[i]-X[j]); d = min(d, L-d);
                    if(ptime+d<=T[i]) 
                        dp[i][j][t+1][0] = min(dp[i][j][t+1][0], ptime+d);
                    else 
                        dp[i][j][t][0] = min(dp[i][j][t][0], ptime+d);
                }
                if(j != 0)
                {
                    ptime = dp[i][j-1][t][0];
                    d = abs(X[j]-X[i]); d = min(d, L-d);
                    if(ptime+d<=T[j]) 
                        dp[i][j][t+1][1] = min(dp[i][j][t+1][1], ptime+d);
                    else 
                        dp[i][j][t][1] = min(dp[i][j][t][1], ptime+d);

                    ptime = dp[i][j-1][t][1];
                    d = abs(X[j]-X[j-1]); d = min(d, L-d);
                    if(ptime+d<=T[j]) 
                        dp[i][j][t+1][1] = min(dp[i][j][t+1][1], ptime+d);
                    else 
                        dp[i][j][t][1] = min(dp[i][j][t][1], ptime+d);
                }
                if(dp[i][j][t][0] < INF || dp[i][j][t][1] <INF)
                    ans = max(ans, t);
                //printf("%d %d %d %lld %lld\n",i,j,t, dp[i][j][t][0], dp[i][j][t][1]);
            }
        }
    }
    for(int i=1; i<=N; ++i)
        for(int j=0; j<=N; ++j)
            if(dp[i][i][j][0]<INF || dp[i][i][j][1]<INF)
                ans = max(ans, j);
    printf("%d\n", ans);
}

Compilation message (stderr)

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &L);
     ~~~~~^~~~~~~~~~~~~~~~
ho_t3.cpp:14:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1; i<=N; ++i) scanf("%d", X+i);
                             ~~~~~^~~~~~~~~~~
ho_t3.cpp:15:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1; i<=N; ++i) scanf("%d", T+i);
                             ~~~~~^~~~~~~~~~~

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