Submission #284411

#	Time	Username	Problem	Language	Result	Execution time	Memory
284411		kshitij_sodani	Triple Jump (JOI19_jumps)	C++14	27 / 100	30 ms	9452 KiB

jumps

//#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
• Subtask 2: 0 / 14
• Subtask 3: 27 / 27
• Subtask 4: 0 / 54