oj.uz

Submission #1045791

# Submission time Handle Problem Language Result Execution time Memory
1045791 2024-08-06T07:44:23 Z hirayuu_oj Uplifting Excursion (BOI22_vault) C++17
5 / 100
 742 ms 524288 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<vector<ll>> dp(M+2,vector<ll>(mx+1,-(1LL<<60)));
    dp[M+1][0]=0;
    for(ll i=M; i>0; i--) {
        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[i+1][k]-cnt) {
                    deq.pop_front();
                }
                deq.push_front({dp[i+1][k]-cnt,cnt});
                if(deq.back().second<cnt-A[M+i])deq.pop_back();
                dp[i][k]=deq.back().first+cnt;
                cnt++;
            }
        }
    }
    vector<vector<ll>> dp2(M+2,vector<ll>(mx+1,-(1LL<<60)));
    dp2[M+1][0]=0;
    for(ll i=M; i>0; i--) {
        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[i+1][k]-cnt) {
                    deq.pop_front();
                }
                deq.push_front({dp2[i+1][k]-cnt,cnt});
                if(deq.back().second<cnt-A[M-i])deq.pop_back();
                dp2[i][k]=deq.back().first+cnt;
                cnt++;
            }
        }
    }
    ll ans=-(1LL<<60);
    rng(i,L,mx) {
        ans=max(ans,dp[1][i]+dp2[1][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 41 ms 42500 KB Output is correct
2 Correct 48 ms 52104 KB Output is correct
3 Correct 30 ms 33296 KB Output is correct
4 Correct 145 ms 117772 KB Output is correct
5 Correct 742 ms 493572 KB Output is correct
6 Correct 656 ms 493568 KB Output is correct
7 Correct 658 ms 493560 KB Output is correct
8 Correct 627 ms 493536 KB Output is correct
9 Correct 644 ms 493560 KB Output is correct
10 Correct 692 ms 493564 KB Output is correct
11 Correct 691 ms 493532 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 42500 KB Output is correct
2 Correct 48 ms 52104 KB Output is correct
3 Correct 30 ms 33296 KB Output is correct
4 Correct 145 ms 117772 KB Output is correct
5 Correct 742 ms 493572 KB Output is correct
6 Correct 656 ms 493568 KB Output is correct
7 Correct 658 ms 493560 KB Output is correct
8 Correct 627 ms 493536 KB Output is correct
9 Correct 644 ms 493560 KB Output is correct
10 Correct 692 ms 493564 KB Output is correct
11 Correct 691 ms 493532 KB Output is correct
12 Correct 29 ms 42504 KB Output is correct
13 Correct 43 ms 51992 KB Output is correct
14 Correct 22 ms 33292 KB Output is correct
15 Correct 132 ms 117744 KB Output is correct
16 Correct 618 ms 493564 KB Output is correct
17 Correct 618 ms 493564 KB Output is correct
18 Correct 665 ms 493620 KB Output is correct
19 Correct 626 ms 493564 KB Output is correct
20 Correct 636 ms 493564 KB Output is correct
21 Correct 689 ms 493764 KB Output is correct
22 Correct 684 ms 493572 KB Output is correct
23 Runtime error 684 ms 524288 KB Execution killed with signal 9
24 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 117752 KB Output is correct
2 Incorrect 419 ms 306396 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 133 ms 117752 KB Output is correct
2 Incorrect 419 ms 306396 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 133 ms 117752 KB Output is correct
2 Incorrect 419 ms 306396 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 41 ms 42500 KB Output is correct
2 Correct 48 ms 52104 KB Output is correct
3 Correct 30 ms 33296 KB Output is correct
4 Correct 145 ms 117772 KB Output is correct
5 Correct 742 ms 493572 KB Output is correct
6 Correct 656 ms 493568 KB Output is correct
7 Correct 658 ms 493560 KB Output is correct
8 Correct 627 ms 493536 KB Output is correct
9 Correct 644 ms 493560 KB Output is correct
10 Correct 692 ms 493564 KB Output is correct
11 Correct 691 ms 493532 KB Output is correct
12 Correct 133 ms 117752 KB Output is correct
13 Incorrect 419 ms 306396 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 133 ms 117752 KB Output is correct
2 Incorrect 419 ms 306396 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 41 ms 42500 KB Output is correct
2 Correct 48 ms 52104 KB Output is correct
3 Correct 30 ms 33296 KB Output is correct
4 Correct 145 ms 117772 KB Output is correct
5 Correct 742 ms 493572 KB Output is correct
6 Correct 656 ms 493568 KB Output is correct
7 Correct 658 ms 493560 KB Output is correct
8 Correct 627 ms 493536 KB Output is correct
9 Correct 644 ms 493560 KB Output is correct
10 Correct 692 ms 493564 KB Output is correct
11 Correct 691 ms 493532 KB Output is correct
12 Correct 29 ms 42504 KB Output is correct
13 Correct 43 ms 51992 KB Output is correct
14 Correct 22 ms 33292 KB Output is correct
15 Correct 132 ms 117744 KB Output is correct
16 Correct 618 ms 493564 KB Output is correct
17 Correct 618 ms 493564 KB Output is correct
18 Correct 665 ms 493620 KB Output is correct
19 Correct 626 ms 493564 KB Output is correct
20 Correct 636 ms 493564 KB Output is correct
21 Correct 689 ms 493764 KB Output is correct
22 Correct 684 ms 493572 KB Output is correct
23 Runtime error 684 ms 524288 KB Execution killed with signal 9
24 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 117752 KB Output is correct
2 Incorrect 419 ms 306396 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 41 ms 42500 KB Output is correct
2 Correct 48 ms 52104 KB Output is correct
3 Correct 30 ms 33296 KB Output is correct
4 Correct 145 ms 117772 KB Output is correct
5 Correct 742 ms 493572 KB Output is correct
6 Correct 656 ms 493568 KB Output is correct
7 Correct 658 ms 493560 KB Output is correct
8 Correct 627 ms 493536 KB Output is correct
9 Correct 644 ms 493560 KB Output is correct
10 Correct 692 ms 493564 KB Output is correct
11 Correct 691 ms 493532 KB Output is correct
12 Correct 29 ms 42504 KB Output is correct
13 Correct 43 ms 51992 KB Output is correct
14 Correct 22 ms 33292 KB Output is correct
15 Correct 132 ms 117744 KB Output is correct
16 Correct 618 ms 493564 KB Output is correct
17 Correct 618 ms 493564 KB Output is correct
18 Correct 665 ms 493620 KB Output is correct
19 Correct 626 ms 493564 KB Output is correct
20 Correct 636 ms 493564 KB Output is correct
21 Correct 689 ms 493764 KB Output is correct
22 Correct 684 ms 493572 KB Output is correct
23 Runtime error 684 ms 524288 KB Execution killed with signal 9
24 Halted 0 ms 0 KB -