Submission #402507

#	Time	Username	Problem	Language	Result	Execution time	Memory
402507		AmineWeslati	Triple Jump (JOI19_jumps)	C++14	19 / 100	3508 ms	137404 KiB

jumps

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int>vi;
#define pb push_back
#define sz(v) (int)v.size()

#define FOR(i,a,b) for(int i=a; i<b; i++)
#define ROF(i,a,b) for(int i=b-1; i>=a; i--)

void IO(){
#ifdef LOCAL
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
#endif
}
//-----------------------------------------------//

void ckmax(int &x, int y){
	x=max(x,y);
}

const int MX=5e3+10;

int N,v[MX][MX];
vi a(MX);

void precompute(){
	FOR(r,2,N){
		int j=r-1;
		multiset<int,greater<int>>s;
		ROF(l,0,r){
			int m=(l+r)/2;
			while(j>m){
				s.erase(s.find(a[j])); 
				j--;
			}

			if(r-l>=2){
				v[l][r]=*s.begin()+a[l]+a[r];
			}

			s.insert(a[l]);
		}
	}

	ROF(l,0,N) FOR(r,l+2,N){
		if(l) ckmax(v[l-1][r],v[l][r]);
		if(r+1<N) ckmax(v[l][r+1],v[l][r]);
	}
}

int main(){
	IO();

	cin>>N;
	FOR(i,0,N) cin>>a[i];

	precompute();

	int Q; cin>>Q;
	FOR(i,0,Q){
		int l,r; cin>>l>>r;
		l--; r--;
		cout << v[l][r] << endl;
	}



}

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 0 / 27
• Subtask 4: 0 / 54