제출 #540945

#제출 시각아이디문제언어결과실행 시간메모리
540945PixelCatCollecting Stamps 3 (JOI20_ho_t3)C++14
100 / 100
158 ms145392 KiB
/* code by the cute ~~Dengdualang~~ PixelCat owo */
/*     as cute as nacho neko (aka. my wife)!     */

/*     Nhade stay for a night here               */
/*     183234 deng deng deng pixelcat oops       */
/*     (yang wang yesu)*2                        */
/*     ^ some weird stuff. nvm =w=               */

#pragma GCC optimize("O4,unroll-loops,no-stack-protector")
#include <bits/stdc++.h>
#define int LL  //__int128
#define double long double
using namespace std;
using LL = long long;
using LLL = __int128_t;
using uLL = unsigned long long;
using pii = pair<int, int>;

#define For(i, a, b) for (int i = a; i <= b; i++)
#define Fors(i, a, b, s) for (int i = a; i <= b; i += s)
#define Forr(i, a, b) for (int i = a; i >= b; i--)
#define F first
#define S second
#define L(id) (id * 2 + 1)
#define R(id) (id * 2 + 2)
#define LO(x) (x & (-x))

#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define mkp make_pair

#define MOD (int)(998244353)
// #define MOD (int)((LL)1e9 + 7)
#define INF (int)(4e18)
// #define INF 1e9
#define EPS (1e-6)

#ifdef NYAOWO
#include "library/debug.hpp"
inline void USACO(const string &s) {
    cerr << "USACO: " << s << "\n";
}

#else
#define debug(...)
inline void timer() {}
inline void USACO(const string &s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

#endif

inline void NYA() {
    ios::sync_with_stdio(false);
    cin.tie(0);
}
inline int gcd(int a, int b) {
    return __gcd(a, b);
}
inline int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}
int fpow(int b, int p, const int &mod) {
    int ans = 1;
    while (p) {
        if (p & 1) ans = ans * b % mod;
        p >>= 1;
        b = b * b % mod;
    }
    return ans;
}
int fpow(int b, int p) {
    return fpow(b, p, MOD);
}
template <typename T>
inline void chmin(T &_a, const T &_b) {
    if (_b < _a) _a = _b;
}
template <typename T>
inline void chmax(T &_a, const T &_b) {
    if (_b > _a) _a = _b;
}
// mt19937_64 rng(
//     chrono::steady_clock::now().time_since_epoch().count());

const int MAXN=210;

int x[MAXN];
int t[MAXN];
int dp[MAXN][MAXN][2][MAXN];

int32_t main() {
    NYA();
    // nyaacho >/////<
    // miku sama bless me >/////<
    int n,L; cin>>n>>L;
    For(i,1,n) cin>>x[i];
    For(i,1,n) cin>>t[i];
    x[n+1]=L;
    auto dist=[&](int a,int b) -> int{
        int owo=(abs(x[a]-x[b]))%L;
        return min(owo,L-owo);
    };
    memset(dp,0x3f3f3f3f,sizeof(dp));
    dp[n+1][0][0][0]=dp[n+1][0][1][0]=0;
    Forr(l,n+1,2) For(r,0,l-2) For(end,0,1) For(get,0,n){
        auto &now=dp[l][r][end][get];
        if(now>INF) continue;

        int nx;
        if(end) nx=r;
        else nx=l;

        // go to left
        int tm=now+dist(nx,l-1);
        chmin(dp[l-1][r][0][get+(tm<=t[l-1])],tm);

        //go to right
        tm=now+dist(nx,r+1);
        chmin(dp[l][r+1][1][get+(tm<=t[r+1])],tm);
    }
    int ans=0;
    Forr(l,n+1,1) For(r,0,l-1) For(end,0,1) For(get,0,n){
        auto &now=dp[l][r][end][get];
        if(now<INF){
            chmax(ans,get);
        }
    }
    cout<<ans<<"\n";
    // debug(dp[7][0][0][0]);
    // debug(dp[6][0][0][1]);
    // debug(dp[5][0][0][2]);
    // debug(dp[5][1][1][3]);
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...