oj.uz

Submission #284411

# Submission time Handle Problem Language Result Execution time Memory
284411 2020-08-27T11:18:45 Z kshitij_sodani Triple Jump (JOI19_jumps) C++14
27 / 100
 30 ms 9452 KB 
//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
//#define endl '\n' 

llo n;
llo it[500001];
llo aa[500001];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	for(llo i=0;i<n;i++){
		cin>>it[i];
	}
	vector<pair<llo,llo>> ss;

	aa[n-1]=it[n-1];
	for(llo i=n-2;i>=0;i--){
		aa[i]=max(aa[i+1],it[i]);
	}
	llo ans=0;
	for(llo i=0;i<n;i++){
		while(ss.size()){
			if(ss.back().a<it[i]){
				ss.pop_back();
			}
			else{
				break;
			}
		}
		if(ss.size()){
			llo ind=i-ss.back().b+i;
			if(i<n){
				ans=max(ans,it[i]+ss.back().a+aa[ind]);
			}
		}
		ss.pb({it[i],i});
	}
	ss.clear();
	for(llo i=n-1;i>=0;i--){
		while(ss.size()){
			if(ss.back().a<it[i]){
				ss.pop_back();
			}
			else{
				break;
			}
		}
		if(ss.size()){
			llo ind=ss.back().b-i+ss.back().b;
			if(i<n){
				ans=max(ans,it[i]+ss.back().a+aa[ind]);
			}
		}
		ss.pb({it[i],i});
	}
	llo q;
	cin>>q;
	while(q--){
		llo cc,dd;
		cin>>cc>>dd;
		cc--;
		dd--;
		cout<<ans<<endl;
	}






 
	return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 14.0

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

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 5276 KB Output is correct
2 Correct 30 ms 9452 KB Output is correct
3 Correct 30 ms 9452 KB Output is correct
4 Correct 30 ms 5288 KB Output is correct
5 Correct 30 ms 5248 KB Output is correct
6 Correct 26 ms 4608 KB Output is correct
7 Correct 25 ms 4472 KB Output is correct
8 Correct 25 ms 4480 KB Output is correct
9 Correct 28 ms 4736 KB Output is correct

Subtask #4
0 / 54.0

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