Submission #1271612

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271612		cokalhado	Collecting Stamps 3 (JOI20_ho_t3)	C++20	100 / 100	71 ms	127304 KiB

ho_t3

// https://oj.uz/problem/view/JOI20_ho_t3?locale=en
#include<bits/stdc++.h>
using namespace std;

#define int long long

// have a dp[N][N][N][2] -> minimum time to collect x stamps, with the furthest right being i and left j
// where right clockwise and left counter-clockwise      and wether I'm at the left or right position
// h = 0 -> I'm in the right
const int inf = 1e18;
const int maxn = 201;
int dp[maxn][maxn][maxn][2];
int N, L;
int X[maxn];
int T[maxn];
int ans;

int32_t main()
{
    cin >> N >> L;
    for(int i = 0; i < N; i++)
    {
        cin >> X[i];
    }
    for(int i = 0; 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 h = 0; h < 2; h++) dp[i][j][k][h] = inf;
    dp[0][0][0][0] = 0;
    dp[0][0][0][1] = 0;

    // push dp
    for(int i = 0; i <= N; i++)
    {
        for(int j = 0; i+j <= N; j++)
        {
            for(int k = 0; k <= i+j; k++)
            {
                for(int h = 0; h < 2; h++)
                {
                    int t = dp[i][j][k][h];
                    if(t < 1e15)
                    {
                        ans = max(ans, k);
                    }
                    else continue;
                    if(i+j >= N) continue;
                    
                    int pos;
                    if(!h)
                    {
                        if(i == 0) pos = 0;
                        else pos = X[i-1];
                    }
                    else
                    {
                        if(j == 0) pos = 0;
                        else pos = X[N-j];
                    }
                    // cout << "i " << i << " j " << j << " k " << k << " h " << h << " pos " << pos << " t " << t << endl;
                    // looking at guy X[i] and X[N-j-1]
                    // move to the right
                    int rmove;
                    if(pos > X[i]) rmove = X[i]+L-pos;
                    else rmove = X[i]-pos;
                    if(rmove+t <= T[i])
                    {
                        dp[i+1][j][k+1][0] = min(dp[i+1][j][k+1][0], rmove+t);
                    }
                    dp[i+1][j][k][0] = min(dp[i+1][j][k][0], rmove+t);

                    // move to the left
                    int lmove;
                    if(pos < X[N-j-1]) lmove = L-X[N-j-1]+pos;
                    else lmove = pos-X[N-j-1];
                    if(lmove+t <= T[N-j-1])
                    {
                        dp[i][j+1][k+1][1] = min(dp[i][j+1][k+1][1], lmove+t);
                    }
                    dp[i][j+1][k][1] = min(dp[i][j+1][k][1], lmove+t);
                }
            }
        }
    }
    cout << ans;
    return 0;
}

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