#include<bits/stdc++.h>
using namespace std;
const int N=200005;
int sp[20][N],dp[5005][5005];
void build(int n){
for(int j=1;j<20;j++){
for(int i=0;i+(1<<j)<=n;i++){
sp[j][i]=max(sp[j-1][i],sp[j-1][i+(1<<(j-1))]);
}
}
}
int RMQ(int l,int r){
int sz=__lg(r-l+1);
return max(sp[sz][l],sp[sz][r-(1<<sz)+1]);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,ans=0;
cin>>n;
for(int i=0;i<n;i++)cin>>sp[0][i];
build(n);
if(n<=5000){
for(int sz=2;sz<n;sz++){
for(int i=0;i+sz<n;i++){
dp[i][i+sz]=sp[0][i]+sp[0][i+sz]+RMQ(i+1,(i+sz+i)/2);
dp[i][i+sz]=max({dp[i][i+sz],dp[i+1][i+sz],dp[i][i+sz-1]});
}
}
ans=dp[0][n-1];
}else{
vector<pair<int,int>>seg;
vector<int>st;// decreasing stack
for(int i=0;i<n;i++){
while(!st.empty()&&sp[0][i]>=sp[0][st.back()]){
seg.push_back({st.back(),i});
st.pop_back();
}
if(!st.empty())seg.push_back({st.back(),i});
st.push_back(i);
}
sort(seg.begin(),seg.end());
for(int i=0;i<seg.size();i++){
int l=seg[i].first,r=seg[i].second;
if(2*r-l<n)ans=max(ans,sp[0][l]+sp[0][r]+RMQ(2*r-l,n-1));
}
}
int q;
cin>>q;
while(q--){
int l,r;
cin>>l>>r;
l--;r--;
if(l==0&&r==n-1)cout<<ans<<"\n";
else cout<<dp[l][r]<<"\n";
}
return 0;
}
Compilation message
jumps.cpp: In function 'int main()':
jumps.cpp:45:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for(int i=0;i<seg.size();i++){
| ~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
724 KB |
Output is correct |
3 |
Correct |
1 ms |
724 KB |
Output is correct |
4 |
Correct |
1 ms |
724 KB |
Output is correct |
5 |
Correct |
1 ms |
724 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
1 ms |
724 KB |
Output is correct |
8 |
Correct |
1 ms |
724 KB |
Output is correct |
9 |
Correct |
1 ms |
724 KB |
Output is correct |
10 |
Correct |
1 ms |
716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
724 KB |
Output is correct |
3 |
Correct |
1 ms |
724 KB |
Output is correct |
4 |
Correct |
1 ms |
724 KB |
Output is correct |
5 |
Correct |
1 ms |
724 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
1 ms |
724 KB |
Output is correct |
8 |
Correct |
1 ms |
724 KB |
Output is correct |
9 |
Correct |
1 ms |
724 KB |
Output is correct |
10 |
Correct |
1 ms |
716 KB |
Output is correct |
11 |
Correct |
337 ms |
73176 KB |
Output is correct |
12 |
Correct |
345 ms |
73108 KB |
Output is correct |
13 |
Correct |
305 ms |
73056 KB |
Output is correct |
14 |
Correct |
325 ms |
73100 KB |
Output is correct |
15 |
Correct |
332 ms |
73240 KB |
Output is correct |
16 |
Correct |
354 ms |
72528 KB |
Output is correct |
17 |
Correct |
366 ms |
72460 KB |
Output is correct |
18 |
Correct |
369 ms |
72444 KB |
Output is correct |
19 |
Correct |
336 ms |
73084 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
54 ms |
19296 KB |
Output is correct |
2 |
Correct |
39 ms |
17284 KB |
Output is correct |
3 |
Correct |
34 ms |
18484 KB |
Output is correct |
4 |
Correct |
50 ms |
19420 KB |
Output is correct |
5 |
Correct |
52 ms |
19376 KB |
Output is correct |
6 |
Correct |
57 ms |
18704 KB |
Output is correct |
7 |
Correct |
47 ms |
18652 KB |
Output is correct |
8 |
Correct |
47 ms |
18532 KB |
Output is correct |
9 |
Correct |
46 ms |
18904 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
724 KB |
Output is correct |
3 |
Correct |
1 ms |
724 KB |
Output is correct |
4 |
Correct |
1 ms |
724 KB |
Output is correct |
5 |
Correct |
1 ms |
724 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
1 ms |
724 KB |
Output is correct |
8 |
Correct |
1 ms |
724 KB |
Output is correct |
9 |
Correct |
1 ms |
724 KB |
Output is correct |
10 |
Correct |
1 ms |
716 KB |
Output is correct |
11 |
Correct |
337 ms |
73176 KB |
Output is correct |
12 |
Correct |
345 ms |
73108 KB |
Output is correct |
13 |
Correct |
305 ms |
73056 KB |
Output is correct |
14 |
Correct |
325 ms |
73100 KB |
Output is correct |
15 |
Correct |
332 ms |
73240 KB |
Output is correct |
16 |
Correct |
354 ms |
72528 KB |
Output is correct |
17 |
Correct |
366 ms |
72460 KB |
Output is correct |
18 |
Correct |
369 ms |
72444 KB |
Output is correct |
19 |
Correct |
336 ms |
73084 KB |
Output is correct |
20 |
Correct |
54 ms |
19296 KB |
Output is correct |
21 |
Correct |
39 ms |
17284 KB |
Output is correct |
22 |
Correct |
34 ms |
18484 KB |
Output is correct |
23 |
Correct |
50 ms |
19420 KB |
Output is correct |
24 |
Correct |
52 ms |
19376 KB |
Output is correct |
25 |
Correct |
57 ms |
18704 KB |
Output is correct |
26 |
Correct |
47 ms |
18652 KB |
Output is correct |
27 |
Correct |
47 ms |
18532 KB |
Output is correct |
28 |
Correct |
46 ms |
18904 KB |
Output is correct |
29 |
Runtime error |
134 ms |
35780 KB |
Execution killed with signal 11 |
30 |
Halted |
0 ms |
0 KB |
- |