Submission #564090

#	Time	Username	Problem	Language	Result	Execution time	Memory
564090		hibiki	Collecting Stamps 3 (JOI20_ho_t3)	C++11	100 / 100	117 ms	130820 KiB

ho_t3

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

long long n,l;
long long xl[205],xr[205],lt[205],rt[205];
long long dp[205][205][205][2];

int main()
{
    scanf("%lld %lld",&n,&l);
    for(int i = 1; i <= n; i++)
    {
        scanf("%lld",&xr[i]);
        xl[n - i + 1] = l - xr[i];
    }
    for(int i = 1; i <= n; i++)
    {
        scanf("%lld",&rt[i]);
        lt[n - i + 1] = rt[i];
    }
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= n; j++)
            for(int k = 0; k <= n; k++)
                dp[i][j][k][0] = dp[i][j][k][1] = 1e18;
    dp[0][0][0][0] = dp[0][0][0][1] = 0;
    int ans = 0;
    for(int k = 0; k <= n; k++)
    {
        for(int i = 0; i <= n; i++)
        {
            for(int j = 0; j <= n; j++)
            {
                if(i + j > n) continue;

                if(dp[i][j][k][0] != 1e18 || dp[i][j][k][1] != 1e18)
                    ans = max(ans,k);

                long long nw_t;

                if(i + 1 <= n)
                {
                    // left to left
                    nw_t = dp[i][j][k][0];
                    nw_t += xl[i + 1] - xl[i];
                    if(nw_t <= lt[i + 1])
                        dp[i + 1][j][k + 1][0] = min(dp[i + 1][j][k + 1][0], nw_t);
                    else
                        dp[i + 1][j][k][0] = min(dp[i + 1][j][k][0], nw_t);
                    // right to left
                    nw_t = dp[i][j][k][1];
                    nw_t += xl[i + 1] + xr[j];
                    if(nw_t <= lt[i + 1])
                        dp[i + 1][j][k + 1][0] = min(dp[i + 1][j][k + 1][0], nw_t);
                    else
                        dp[i + 1][j][k][0] = min(dp[i + 1][j][k][0], nw_t);
                }

                if(j + 1 <= n)
                {
                    // left to right
                    nw_t = dp[i][j][k][0];
                    nw_t += xr[j + 1] + xl[i];
                    if(nw_t <= rt[j + 1])
                        dp[i][j + 1][k + 1][1] = min(dp[i][j + 1][k + 1][1], nw_t);
                    else
                        dp[i][j + 1][k][1] = min(dp[i][j + 1][k][1], nw_t);
                    // right to right
                    nw_t = dp[i][j][k][1];
                    nw_t += xr[j + 1] - xr[j];
                    if(nw_t <= rt[j + 1])
                        dp[i][j + 1][k + 1][1] = min(dp[i][j + 1][k + 1][1], nw_t);
                    else
                        dp[i][j + 1][k][1] = min(dp[i][j + 1][k][1], nw_t);
                }
            }
        }
    }

    printf("%d\n",ans);
    return 0;
}

Compilation message (stderr)

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     scanf("%lld %lld",&n,&l);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
ho_t3.cpp:13:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |         scanf("%lld",&xr[i]);
      |         ~~~~~^~~~~~~~~~~~~~~
ho_t3.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         scanf("%lld",&rt[i]);
      |         ~~~~~^~~~~~~~~~~~~~~

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