oj.uz

Submission #1045798

# Submission time Handle Problem Language Result Execution time Memory
1045798 2024-08-06T07:47:14 Z hirayuu_oj Uplifting Excursion (BOI22_vault) C++17
20 / 100
 1162 ms 15260 KB 
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0; i<(n); i++)
#define rng(i,l,r) for(ll i=(l); i<(r); i++)
#define all(x) x.begin(),x.end()
using ll=long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll M,L;
    cin>>M>>L;
    vector<ll> A(M*2+1);
    rep(i,M*2+1) {
        cin>>A[i];
    }
    if(L<0) {
        L=-L;
        rep(i,M) {
            swap(A[i],A[M*2-i]);
        }
    }
    const ll mx=600000;
    vector<ll> dp(mx+1,-(1LL<<60));
    dp[0]=0;
    for(ll i=M; i>0; i--) {
        vector<ll> ndp(mx+1,-(1LL<<60));
        rep(j,i) {
            ll cnt=0;
            deque<pair<ll,ll>> deq;
            for(ll k=j; k<=mx; k+=i) {
                while(!deq.empty()&&deq.front().first<=dp[k]-cnt) {
                    deq.pop_front();
                }
                deq.push_front({dp[k]-cnt,cnt});
                if(deq.back().second<cnt-A[M+i])deq.pop_back();
                ndp[k]=deq.back().first+cnt;
                cnt++;
            }
        }
        swap(dp,ndp);
    }
    vector<ll> dp2(mx+1,-(1LL<<60));
    dp2[0]=0;
    for(ll i=M; i>0; i--) {
        vector<ll> ndp(mx+1,-(1LL<<60));
        rep(j,i) {
            ll cnt=0;
            deque<pair<ll,ll>> deq;
            for(ll k=j; k<=mx; k+=i) {
                while(!deq.empty()&&deq.front().first<=dp2[k]-cnt) {
                    deq.pop_front();
                }
                deq.push_front({dp2[k]-cnt,cnt});
                if(deq.back().second<cnt-A[M-i])deq.pop_back();
                ndp[k]=deq.back().first+cnt;
                cnt++;
            }
        }
        swap(dp2,ndp);
    }
    ll ans=-(1LL<<60);
    rng(i,L,mx) {
        ans=max(ans,dp[i]+dp2[i-L]+A[M]);
    }
    if(ans<0)cout<<"impossible\n";
    else cout<<ans<<"\n";
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 14392 KB Output is correct
2 Correct 40 ms 14520 KB Output is correct
3 Correct 15 ms 14564 KB Output is correct
4 Correct 118 ms 14496 KB Output is correct
5 Correct 524 ms 14496 KB Output is correct
6 Correct 530 ms 14492 KB Output is correct
7 Correct 551 ms 14520 KB Output is correct
8 Correct 526 ms 14516 KB Output is correct
9 Correct 518 ms 14496 KB Output is correct
10 Correct 569 ms 14432 KB Output is correct
11 Correct 580 ms 14492 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 14392 KB Output is correct
2 Correct 40 ms 14520 KB Output is correct
3 Correct 15 ms 14564 KB Output is correct
4 Correct 118 ms 14496 KB Output is correct
5 Correct 524 ms 14496 KB Output is correct
6 Correct 530 ms 14492 KB Output is correct
7 Correct 551 ms 14520 KB Output is correct
8 Correct 526 ms 14516 KB Output is correct
9 Correct 518 ms 14496 KB Output is correct
10 Correct 569 ms 14432 KB Output is correct
11 Correct 580 ms 14492 KB Output is correct
12 Correct 24 ms 14524 KB Output is correct
13 Correct 36 ms 14512 KB Output is correct
14 Correct 15 ms 14348 KB Output is correct
15 Correct 113 ms 14424 KB Output is correct
16 Correct 505 ms 14500 KB Output is correct
17 Correct 523 ms 14492 KB Output is correct
18 Correct 545 ms 14748 KB Output is correct
19 Correct 507 ms 14492 KB Output is correct
20 Correct 561 ms 14492 KB Output is correct
21 Correct 594 ms 14496 KB Output is correct
22 Correct 570 ms 14444 KB Output is correct
23 Correct 1043 ms 14492 KB Output is correct
24 Correct 1067 ms 14528 KB Output is correct
25 Correct 1150 ms 14528 KB Output is correct
26 Correct 1070 ms 14524 KB Output is correct
27 Correct 1078 ms 14296 KB Output is correct
28 Correct 1162 ms 14524 KB Output is correct
29 Correct 1150 ms 14528 KB Output is correct

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 14492 KB Output is correct
2 Incorrect 344 ms 15260 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 14492 KB Output is correct
2 Incorrect 344 ms 15260 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 14492 KB Output is correct
2 Incorrect 344 ms 15260 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 14392 KB Output is correct
2 Correct 40 ms 14520 KB Output is correct
3 Correct 15 ms 14564 KB Output is correct
4 Correct 118 ms 14496 KB Output is correct
5 Correct 524 ms 14496 KB Output is correct
6 Correct 530 ms 14492 KB Output is correct
7 Correct 551 ms 14520 KB Output is correct
8 Correct 526 ms 14516 KB Output is correct
9 Correct 518 ms 14496 KB Output is correct
10 Correct 569 ms 14432 KB Output is correct
11 Correct 580 ms 14492 KB Output is correct
12 Correct 112 ms 14492 KB Output is correct
13 Incorrect 344 ms 15260 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 14492 KB Output is correct
2 Incorrect 344 ms 15260 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 14392 KB Output is correct
2 Correct 40 ms 14520 KB Output is correct
3 Correct 15 ms 14564 KB Output is correct
4 Correct 118 ms 14496 KB Output is correct
5 Correct 524 ms 14496 KB Output is correct
6 Correct 530 ms 14492 KB Output is correct
7 Correct 551 ms 14520 KB Output is correct
8 Correct 526 ms 14516 KB Output is correct
9 Correct 518 ms 14496 KB Output is correct
10 Correct 569 ms 14432 KB Output is correct
11 Correct 580 ms 14492 KB Output is correct
12 Correct 24 ms 14524 KB Output is correct
13 Correct 36 ms 14512 KB Output is correct
14 Correct 15 ms 14348 KB Output is correct
15 Correct 113 ms 14424 KB Output is correct
16 Correct 505 ms 14500 KB Output is correct
17 Correct 523 ms 14492 KB Output is correct
18 Correct 545 ms 14748 KB Output is correct
19 Correct 507 ms 14492 KB Output is correct
20 Correct 561 ms 14492 KB Output is correct
21 Correct 594 ms 14496 KB Output is correct
22 Correct 570 ms 14444 KB Output is correct
23 Correct 1043 ms 14492 KB Output is correct
24 Correct 1067 ms 14528 KB Output is correct
25 Correct 1150 ms 14528 KB Output is correct
26 Correct 1070 ms 14524 KB Output is correct
27 Correct 1078 ms 14296 KB Output is correct
28 Correct 1162 ms 14524 KB Output is correct
29 Correct 1150 ms 14528 KB Output is correct
30 Correct 112 ms 14492 KB Output is correct
31 Incorrect 344 ms 15260 KB Output isn't correct
32 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 14492 KB Output is correct
2 Incorrect 344 ms 15260 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 14392 KB Output is correct
2 Correct 40 ms 14520 KB Output is correct
3 Correct 15 ms 14564 KB Output is correct
4 Correct 118 ms 14496 KB Output is correct
5 Correct 524 ms 14496 KB Output is correct
6 Correct 530 ms 14492 KB Output is correct
7 Correct 551 ms 14520 KB Output is correct
8 Correct 526 ms 14516 KB Output is correct
9 Correct 518 ms 14496 KB Output is correct
10 Correct 569 ms 14432 KB Output is correct
11 Correct 580 ms 14492 KB Output is correct
12 Correct 24 ms 14524 KB Output is correct
13 Correct 36 ms 14512 KB Output is correct
14 Correct 15 ms 14348 KB Output is correct
15 Correct 113 ms 14424 KB Output is correct
16 Correct 505 ms 14500 KB Output is correct
17 Correct 523 ms 14492 KB Output is correct
18 Correct 545 ms 14748 KB Output is correct
19 Correct 507 ms 14492 KB Output is correct
20 Correct 561 ms 14492 KB Output is correct
21 Correct 594 ms 14496 KB Output is correct
22 Correct 570 ms 14444 KB Output is correct
23 Correct 1043 ms 14492 KB Output is correct
24 Correct 1067 ms 14528 KB Output is correct
25 Correct 1150 ms 14528 KB Output is correct
26 Correct 1070 ms 14524 KB Output is correct
27 Correct 1078 ms 14296 KB Output is correct
28 Correct 1162 ms 14524 KB Output is correct
29 Correct 1150 ms 14528 KB Output is correct
30 Correct 112 ms 14492 KB Output is correct
31 Incorrect 344 ms 15260 KB Output isn't correct
32 Halted 0 ms 0 KB -