Submission #373173

#TimeUsernameProblemLanguageResultExecution timeMemory
373173Leonardo_PaesCollecting Stamps 3 (JOI20_ho_t3)C++17
100 / 100
195 ms134124 KiB
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e2+10;
typedef long long ll;
const ll inf = 1e18;
ll dp[maxn][maxn][maxn][2], x[maxn], t[maxn];

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    ll n, l;
    cin >> n >> l;
    for(int i=1; i<=n; i++) cin >> x[i];
    for(int i=1; i<=n; i++) cin >> t[i];
    for(int i=0; i<=n; i++){
        for(int j=0; j<=n; j++){
            for(int k=0; k<=n; k++){
                dp[i][j][k][0] = dp[i][j][k][1] = inf;
            }
        }
    }
    dp[0][0][0][0] = dp[0][0][0][1] = 0;
    auto prv = [&](ll x){
        if(x-1 < 1) return n;
        return x-1;
    };
    auto nxt = [&](ll x){
        if(x+1 > n) return 1LL;
        return x+1;
    };
    auto d = [&](ll a, ll b){
        if(a > b) swap(a, b);
        return min(x[b] - x[a], l - x[b] + x[a]);
    };
    auto min_self = [&](ll &a, ll &b){
        a = min(a, b);
    };
    for(ll len=0; len<n; len++){
        for(ll i=0; i<=n; i++){
            for(ll k=0; k<=len; k++){
                ll j = (i + len)%(n+1);
                //l -> l
                ll tt = dp[i][j][k][0] + d(prv(i), i);
                min_self(dp[prv(i)][j][k+(tt <= t[prv(i)])][0], tt);
                //r -> l
                tt = dp[i][j][k][1] + d(prv(i), j);
                min_self(dp[prv(i)][j][k+(tt <= t[prv(i)])][0], tt);
                //l -> r
                tt = dp[i][j][k][0] + d(i, nxt(j));
                min_self(dp[i][nxt(j)][k+(tt <= t[nxt(j)])][1], tt);
                //r -> r
                tt = dp[i][j][k][1] + d(j, nxt(j));
                min_self(dp[i][nxt(j)][k+(tt <= t[nxt(j)])][1], tt);
            }
        }
    }
    ll ans = 0;
    for(ll i=0; i<=n; i++){
        for(ll j=0; j<=n; j++){
            for(ll k=0; k<=n; k++){
                for(int q : {0, 1}){
                    if(dp[i][j][k][q] != inf) ans = max(ans, k);
                }
            }
        }
    }
    cout << ans << "\n";
    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...