Submission #475939

#	Time	Username	Problem	Language	Result	Execution time	Memory
475939		ymm	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	407 ms	145408 KiB

ho_t3

///
///   Let the voice of love take you higher!
///

#define _USE_MATH_DEFINES
#define FAST ios::sync_with_stdio(false),cin.tie(0);
#include <bits/stdc++.h>
#define Loop(x, l, r) for(ll x = ll(l); x < ll(r); ++x)
#define LoopR(x, l, r) for(ll x = ll(r)-1; x >= ll(l); --x)
#define all(x) x.begin(), x.end()
#define Kill(x) exit((cout << (x) << '\n', 0))
#define YN(flag) ((flag)? "YES": "NO")
#define F first
#define S second
typedef          long long   ll;
typedef unsigned long long  ull;
typedef std::pair<int,int>  pii;
typedef std::pair<ll ,ll >  pll;
using namespace std;

#define int ll

const int N = 210;
ll dp[2][N][N][N]; // d, cnt, l, r
ll len, _x[N], *x = _x+1;
ll _t[N], *t = _t+1;
int n;

ll dis(int i, int j)
{
    return min(abs(x[j]-x[i]), len-abs(x[j]-x[i]));
}

bool gd(int i, int j, ll t)
{
    if(t > 1e10) return 0;
    return dis(i,j)+t <= ::t[j];
}

void smin(ll& x, ll y){x = min(x, y);}

signed main()
{
    FAST;
    cin >> n >> len;
    Loop(i,0,n) cin >> x[i];
    x[n] = x[0]; x[-1] = x[n-1];
    Loop(i,0,n) cin >> t[i];
    t[n] = t[0]; t[-1] = t[n-1];
    memset(dp, 31, sizeof dp);
    dp[0][t[0  ]>=    x[  0]][1][n  ] =     x[  0];
    dp[0][t[0  ]>=    x[  0]][1][n  ] =     x[  0];
    dp[1][t[n-1]>=len-x[n-1]][0][n-1] = len-x[n-1];
    dp[1][t[n-1]>=len-x[n-1]][0][n-1] = len-x[n-1];
    LoopR(k,1,n)
    {
        Loop(l,0,n-k+1)
        {
            int r = l+k;
            Loop(cnt,0,n)
            {
                smin(dp[0][cnt+gd(l-1,l  ,dp[0][cnt][l][r])][l+1][r], dp[0][cnt][l][r]+dis(l-1,l  ));
                smin(dp[1][cnt+gd(l-1,r-1,dp[0][cnt][l][r])][l][r-1], dp[0][cnt][l][r]+dis(l-1,r-1));
                smin(dp[0][cnt+gd(r  ,l  ,dp[1][cnt][l][r])][l+1][r], dp[1][cnt][l][r]+dis(r  ,l  ));
                smin(dp[1][cnt+gd(r  ,r-1,dp[1][cnt][l][r])][l][r-1], dp[1][cnt][l][r]+dis(r  ,r-1));
            }
        }
    }
    int ans = 0;
    Loop(i,0,n+1) Loop(cnt,ans+1,n+1)
    {
        if(dp[0][cnt][i][i] < 1e10) ans = cnt;
        if(dp[1][cnt][i][i] < 1e10) ans = cnt;
    }
    cout << ans << '\n';
}

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