oj.uz

Submission #940940

# Submission time Handle Problem Language Result Execution time Memory
940940 2024-03-08T02:53:00 Z LittleOrange Collecting Stamps 3 (JOI20_ho_t3) C++17
100 / 100
 486 ms 511568 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 604 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 1 ms 600 KB Output is correct
25 Correct 1 ms 616 KB Output is correct
26 Correct 1 ms 600 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 604 KB Output is correct
30 Correct 1 ms 604 KB Output is correct
31 Correct 1 ms 604 KB Output is correct
32 Correct 0 ms 604 KB Output is correct
33 Correct 1 ms 604 KB Output is correct
34 Correct 1 ms 604 KB Output is correct
35 Correct 1 ms 604 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 365 ms 367848 KB Output is correct
19 Correct 151 ms 173392 KB Output is correct
20 Correct 61 ms 67420 KB Output is correct
21 Correct 138 ms 159128 KB Output is correct
22 Correct 215 ms 235140 KB Output is correct
23 Correct 51 ms 52816 KB Output is correct
24 Correct 34 ms 36672 KB Output is correct
25 Correct 53 ms 51284 KB Output is correct
26 Correct 12 ms 12084 KB Output is correct
27 Correct 56 ms 54692 KB Output is correct
28 Correct 34 ms 32896 KB Output is correct
29 Correct 54 ms 56328 KB Output is correct
30 Correct 39 ms 39348 KB Output is correct
31 Correct 50 ms 51352 KB Output is correct
32 Correct 19 ms 19580 KB Output is correct
33 Correct 51 ms 51292 KB Output is correct
34 Correct 9 ms 11064 KB Output is correct
35 Correct 45 ms 49732 KB Output is correct
36 Correct 18 ms 16396 KB Output is correct
37 Correct 55 ms 54696 KB Output is correct
38 Correct 23 ms 22244 KB Output is correct
39 Correct 53 ms 58200 KB Output is correct
40 Correct 29 ms 25948 KB Output is correct
41 Correct 486 ms 503920 KB Output is correct
42 Correct 246 ms 278088 KB Output is correct
43 Correct 446 ms 503680 KB Output is correct
44 Correct 236 ms 273232 KB Output is correct
45 Correct 431 ms 503892 KB Output is correct
46 Correct 232 ms 278104 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 1 ms 600 KB Output is correct
25 Correct 1 ms 616 KB Output is correct
26 Correct 1 ms 600 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 604 KB Output is correct
30 Correct 1 ms 604 KB Output is correct
31 Correct 1 ms 604 KB Output is correct
32 Correct 0 ms 604 KB Output is correct
33 Correct 1 ms 604 KB Output is correct
34 Correct 1 ms 604 KB Output is correct
35 Correct 1 ms 604 KB Output is correct
36 Correct 365 ms 367848 KB Output is correct
37 Correct 151 ms 173392 KB Output is correct
38 Correct 61 ms 67420 KB Output is correct
39 Correct 138 ms 159128 KB Output is correct
40 Correct 215 ms 235140 KB Output is correct
41 Correct 51 ms 52816 KB Output is correct
42 Correct 34 ms 36672 KB Output is correct
43 Correct 53 ms 51284 KB Output is correct
44 Correct 12 ms 12084 KB Output is correct
45 Correct 56 ms 54692 KB Output is correct
46 Correct 34 ms 32896 KB Output is correct
47 Correct 54 ms 56328 KB Output is correct
48 Correct 39 ms 39348 KB Output is correct
49 Correct 50 ms 51352 KB Output is correct
50 Correct 19 ms 19580 KB Output is correct
51 Correct 51 ms 51292 KB Output is correct
52 Correct 9 ms 11064 KB Output is correct
53 Correct 45 ms 49732 KB Output is correct
54 Correct 18 ms 16396 KB Output is correct
55 Correct 55 ms 54696 KB Output is correct
56 Correct 23 ms 22244 KB Output is correct
57 Correct 53 ms 58200 KB Output is correct
58 Correct 29 ms 25948 KB Output is correct
59 Correct 486 ms 503920 KB Output is correct
60 Correct 246 ms 278088 KB Output is correct
61 Correct 446 ms 503680 KB Output is correct
62 Correct 236 ms 273232 KB Output is correct
63 Correct 431 ms 503892 KB Output is correct
64 Correct 232 ms 278104 KB Output is correct
65 Correct 360 ms 432232 KB Output is correct
66 Correct 315 ms 379984 KB Output is correct
67 Correct 296 ms 355532 KB Output is correct
68 Correct 276 ms 315508 KB Output is correct
69 Correct 370 ms 425444 KB Output is correct
70 Correct 354 ms 399188 KB Output is correct
71 Correct 332 ms 405568 KB Output is correct
72 Correct 359 ms 412204 KB Output is correct
73 Correct 335 ms 367440 KB Output is correct
74 Correct 299 ms 332372 KB Output is correct
75 Correct 316 ms 386128 KB Output is correct
76 Correct 410 ms 474380 KB Output is correct
77 Correct 414 ms 474192 KB Output is correct
78 Correct 277 ms 321112 KB Output is correct
79 Correct 284 ms 337976 KB Output is correct
80 Correct 388 ms 460028 KB Output is correct
81 Correct 286 ms 343784 KB Output is correct
82 Correct 332 ms 373828 KB Output is correct
83 Correct 413 ms 503888 KB Output is correct
84 Correct 323 ms 399084 KB Output is correct
85 Correct 371 ms 452944 KB Output is correct
86 Correct 375 ms 439068 KB Output is correct
87 Correct 320 ms 386320 KB Output is correct
88 Correct 442 ms 511508 KB Output is correct
89 Correct 430 ms 511500 KB Output is correct
90 Correct 322 ms 392676 KB Output is correct
91 Correct 442 ms 511312 KB Output is correct
92 Correct 439 ms 511568 KB Output is correct
93 Correct 405 ms 496208 KB Output is correct