Submission #1324287

#TimeUsernameProblemLanguageResultExecution timeMemory
1324287ivan_alexeevCollecting Stamps 3 (JOI20_ho_t3)C++20
5 / 100
120 ms92484 KiB
#include <bits/stdc++.h>

using namespace std;

#ifndef lisie_bimbi
#define endl '\n'
#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,bmi2,fma")
#endif

using ll = long long;
const ll inf = 1'000'000'000'000'000'000;

#define int long long

int n, l;
vector<int> x, t;

int dist(int a, int b){
    if(b < a){
        swap(a, b);
    }
    return min(b - a, l - (b - a));
}

void solve(){
    cin >> n >> l;
    x.resize(n);
    t.resize(n);
    for(int i = 0; i < n; i++){
        cin >> x[i];
    }
    for(int i = 0; i < n; i++){
        cin >> t[i];
    }
    vector<vector<vector<array<int, 2>>>> dp(n, vector<vector<array<int, 2>>>(n, vector<array<int, 2>>(n + 1, {inf, inf})));
    for(int i = 0; i < n; i++){
        dp[i][i][0] = {dist(0, x[i]), dist(0, x[i])};
        if(dist(0, x[i]) <= t[i]){
            dp[i][i][1] = {dist(0, x[i]), dist(0, x[i])};
        }
    }
    for(int sz = 2; sz <= n; sz++){
        for(int l = 0; l < n; l++){
            int r = (l + sz - 1) % n;
            for(int ans = 0; ans <= n; ans++){
                dp[l][r][ans][0] = min(dp[l][r][ans][0], dp[(l + 1) % n][r][ans][0] + dist(x[l], x[(l + 1) % n]));
                dp[l][r][ans][1] = min(dp[l][r][ans][1], dp[l][(r - 1 + n) % n][ans][1] + dist(x[(r - 1 + n) % n], x[r]));
                if(ans > 0){
                    if(dp[(l + 1) % n][r][ans - 1][0] + dist(x[l], x[(l + 1) % n]) <= t[l]){
                        dp[l][r][ans][0] = min(dp[l][r][ans][0], dp[(l + 1) % n][r][ans - 1][0] + dist(x[l], x[(l + 1) % n]));
                    }
                    if(dp[l][(r - 1 + n) % n][ans - 1][1] + dist(x[(r - 1 + n) % n], x[r]) <= t[r]){
                        dp[l][r][ans][1] = min(dp[l][r][ans][1], dp[l][(r - 1 + n) % n][ans - 1][1] + dist(x[(r - 1 + n) % n], x[r]));
                    }
                }
                dp[l][r][ans][0] = min(dp[l][r][ans][0], dp[l][r][ans][1] + dist(x[l], x[r]));
                dp[l][r][ans][0] = min(dp[l][r][ans][0], dp[l][r][ans][1] + dist(x[l], x[r]));
            }
        }
    }
    for(int ans = n; ans >= 0; ans--){
        for(int l = 0; l < n; l++){
            for(int r = 0; r < n; r++){
                if((dp[l][r][ans][0] < inf) || (dp[l][r][ans][1] < inf)){
                    cout << ans << endl;
                    return;
                }
            }
        }
    }
}

signed main(){
#ifdef lisie_bimbi
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
#endif
    cin.tie(nullptr)->sync_with_stdio(false);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...