Submission #1363863

#TimeUsernameProblemLanguageResultExecution timeMemory
1363863paronmanukyanCollecting Stamps 3 (JOI20_ho_t3)C++20
100 / 100
71 ms135308 KiB
#include <bits/stdc++.h>
#define _CRT_SECURE_NO_WARNINGS
using namespace std;

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define sort_uniq(x) sort(all(x)), uniq(x);
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define V vector
#define V2dll V<V<ll>>
#define V2dint V<V<int>>
#define V2dchar V<V<char>>
#define V2dbool V<V<bool>>
#define V3dll V<V<V<ll>>>
#define V3dint V<V<V<int>>>
#define V3dchar V<V<V<char>>>
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define blt __builtin_popcount
#define clr(x) x.clear()
#define ff first
#define ss second
#define popf pop_front
#define popb pop_back
#define sz(x) int(x.size())
#define rep(a,b,c,d) for(int a = b;a <= c; a += d)
#define repl(a,b,c,d) for(int a = b; a >= c; a -= d)

mt19937_64 rng(chrono::steady_clock().now().time_since_epoch().count());

const int N = 205;
const ll INFLL = 1e18;

ll dp[N][N][N][2];
ll x[N];
ll t[N];

void prec() {
    rep(i, 0, N - 1, 1) {
        rep(j, 0, N - 1, 1) {
            rep(k, 0, N - 1, 1) {
                rep(ms, 0, 1, 1) {
                    dp[i][j][k][ms] = INFLL;
                }
            }
        }
    }
}

int main()
{
    FASTIO
    
    prec();
    
    int n; cin >> n;
    ll l; cin >> l;
    
    rep(i, 1, n, 1) cin >> x[i];
    rep(i, 1, n, 1) cin >> t[i];
    
    x[0] = 0; 
    x[n + 1] = l; 
    
    dp[0][n + 1][0][0] = dp[0][n + 1][0][1] = 0;

    rep(i, 0, n, 1) {
        repl(j, n + 1, max(i + 1, 1), 1) { 
            rep(k, 0, n, 1) { 
                if (i == j - 1) continue;
                
                ll tim0 = dp[i][j][k][0];
                ll tim1 = dp[i][j][k][1];

                if (tim0 != INFLL) {
                    ll nt = tim0 + x[i + 1] - x[i];
                    int nk = k + (nt <= t[i + 1] ? 1 : 0);
                    dp[i + 1][j][nk][0] = min(dp[i + 1][j][nk][0], nt);
                }
                if (tim1 != INFLL) {
                    ll nt = tim1 + l - x[j] + x[i + 1];
                    int nk = k + (nt <= t[i + 1] ? 1 : 0);
                    dp[i + 1][j][nk][0] = min(dp[i + 1][j][nk][0], nt);
                }

                if (tim0 != INFLL) {
                    ll nt = tim0 + x[i] + l - x[j - 1];
                    int nk = k + (nt <= t[j - 1] ? 1 : 0);
                    dp[i][j - 1][nk][1] = min(dp[i][j - 1][nk][1], nt);
                }
                if (tim1 != INFLL) {
                    ll nt = tim1 + x[j] - x[j - 1];
                    int nk = k + (nt <= t[j - 1] ? 1 : 0);
                    dp[i][j - 1][nk][1] = min(dp[i][j - 1][nk][1], nt);
                }
            }
        }
    }

    int ans = 0;
    rep(i, 0, n, 1) {
        repl(j, n + 1, max(i, 1), 1) {
            rep(k, 0, n, 1) { 
                rep(it, 0, 1, 1) {
                    if (dp[i][j][k][it] < INFLL) { 
                        ans = max(ans, k);
                    }
                }
            }
        }
    }
    
    cout << ans << "\n";
    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...