Submission #940940

#	Time	Username	Problem	Language	Result	Execution time	Memory
940940		LittleOrange	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	486 ms	511568 KiB

ho_t3

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll big = 1e18;
struct BIT{
    ll n;
    vector<ll> a;
    BIT(ll N):n(N),a(N+1,0){}
    void add(ll i, ll v){
        for(;i<=n;i+=i&-i) a[i] += v;
    }
    ll get(ll i){
        ll r = 0;
        for(;i;i-=i&-i) r += a[i];
        return r;
    }
    ll get(ll l, ll r){
        if(l>r) return 0;
        return get(r)-get(l-1);
    }
};
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    ll n,l;
    cin >> n >> l;
    vector<ll> x(n),t(n);
    for(ll &i : x) cin >> i;
    for(ll &i : t) cin >> i;
    for(ll i = 0;i<n;i++) x.push_back(x[i]+l);
    for(ll i = 0;i<n;i++) t.push_back(t[i]);
    ll n2 = n*2;
    vector<vector<vector<ll>>> dpL(n+1,vector<vector<ll>>(n2,vector<ll>(n2,big))); // l r c
    vector<vector<vector<ll>>> dpR(n+1,vector<vector<ll>>(n2,vector<ll>(n2,big))); // l r c
    for(ll i = 0;i<n;i++){
        if (abs(x[i+n]-l)<=t[i+n]) dpR[1][n][i+n] = abs(x[i+n]-l);
        if (abs(l-x[i])<=t[i]) dpL[1][i][n-1] = abs(l-x[i]);
        for(ll a = n2-1;a>=0;a--){
            for(ll b = a+1;b<n2;b++){
                dpL[1][a][b] = min({dpL[1][a][b],dpL[1][a][b-1],dpL[1][a+1][b]+abs(x[a]-x[a+1])});
                dpR[1][a][b] = min({dpR[1][a][b],dpR[1][a+1][b],dpR[1][a][b-1]+abs(x[b]-x[b-1])});
            }
        }
    }
    for(ll c = 2;c<=n;c++){
        for(ll a = 0;a<n2;a++){
            for(ll b = a+1;b<n2;b++){
                ll t0 = dpR[c-1][a+1][b]+abs(x[b]-x[a]);
                if(t0<=t[a]) dpL[c][a][b] = min(dpL[c][a][b],t0);
                ll t1 = dpL[c-1][a][b-1]+abs(x[b]-x[a]);
                if(t1<=t[b]) dpR[c][a][b] = min(dpR[c][a][b],t1);
                ll t2 = dpL[c-1][a+1][b]+abs(x[a+1]-x[a]);
                if(t2<=t[a]) dpL[c][a][b] = min(dpL[c][a][b],t2);
                ll t3 = dpR[c-1][a][b-1]+abs(x[b]-x[b-1]);
                if(t3<=t[b]) dpR[c][a][b] = min(dpR[c][a][b],t3);
            }
        }
        for(ll a = n2-1;a>=0;a--){
            for(ll b = a+1;b<n2;b++){
                dpL[c][a][b] = min({dpL[c][a][b],dpL[c][a][b-1],dpL[c][a+1][b]+abs(x[a]-x[a+1])});
                dpR[c][a][b] = min({dpR[c][a][b],dpR[c][a+1][b],dpR[c][a][b-1]+abs(x[b]-x[b-1])});
            }
        }
    }
    ll ans = 0;
    for(ll c = 1;c<=n;c++){
        for(ll a = 0;a<n2;a++){
            for(ll b = a;b<n2&&b-a<n;b++){
                if (min(dpL[c][a][b],dpR[c][a][b])<big) ans = max(ans,c);
            }
        }
    }
    /*
    for(ll c = 1;c<=n;c++){
        cout << "c=" << c << "\n";
        for(ll a = 0;a<n2;a++){
            for(ll b = 0;b<n2;b++){
                cout << (dpL[c][a][b]>=big?-1:dpL[c][a][b]) << ",";
                cout << (dpR[c][a][b]>=big?-1:dpR[c][a][b]) << " ";
            }
            cout << "\n";
        }
    }*/
    cout << ans << "\n";
}

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