제출 #475937

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
475937		ymm	Collecting Stamps 3 (JOI20_ho_t3)	C++17	15 / 100	1026 ms	290296 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          __int128    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)
{
    if(x[j] < x[i]) swap(i, j);
    return min(x[j]-x[i], len-(x[j]-x[i]));
}

bool gd(int i, int j, ll t)
{
    //if(dis(i,j)+t <= ::t[j]) cerr << i << ' ' << j << ' ' << t << '\n';
    return dis(i,j)+t <= ::t[j];
}

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

signed main()
{
    FAST;
    long long _n, _len;
    cin >> _n >> _len;
    n = _n; len = _len;
    Loop(i,0,n) {long long z; cin >> z; x[i] = z;}
    x[n] = x[0]; x[-1] = x[n-1];
    Loop(i,0,n) {long long z; cin >> z; t[i] = z;}
    t[n] = t[0]; t[-1] = t[n-1];
    ll inf = 1; inf <<= 100;
    Loop(a,0,2)Loop(b,0,N)Loop(c,0,N)Loop(d,0,N)
        dp[a][b][c][d] = inf;
    dp[0][t[0  ]>=    x[  0]][1][n  ] =     x[  0];
    dp[1][t[0  ]>=    x[  0]][1][n  ] =     x[  0];
    dp[0][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)
        {
            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) Loop(cnt,ans+1,N)
    {
        if(dp[0][cnt][i][i] != inf) ans = cnt;
        if(dp[1][cnt][i][i] != inf) ans = cnt;
    }
    cout << signed(ans) << '\n';
}

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