답안 #1045791

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1045791	2024-08-06T07:44:23 Z	hirayuu_oj	Uplifting Excursion (BOI22_vault)	C++17	5 / 100	742 ms	524288 KB

vault

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #1045791

Compilation message