Submission #942719

#	Time	Username	Problem	Language	Result	Execution time	Memory
942719		Tyx2019	Triple Jump (JOI19_jumps)	C++17	32 / 100	4019 ms	10440 KiB

jumps

#include <bits/stdc++.h>
#define debug(x) if(1) cout << #x << " is " << x << "\n";
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
int getans(int A[], int N){
	vector<pair<int,int>> V;
	for(int i=0;i<N;i++) V.push_back({A[i],i});
	sort(V.begin(), V.end(), greater<pair<int,int>>());
	int lorg = 40;
	vector<int> V2;
	for(int i=0;i<min(lorg,N);i++){
		V2.push_back(V[i].second);
	}
	vector<int> V3;
	for(int i=0;i<N;i++){
		if(V[i].first == V[lorg-1].first) V3.push_back(i);
	}
	int ans = 0;
	if((int)V3.size() > lorg && lorg <= N) ans = V[lorg-1].first * 3;
	else{
		for(auto i:V3){
			if(i>=lorg) V2.push_back(i);
		}
	}
	int sufmax[N];
	//cout << N << "\n";
	//cout << A[N-1] << '\n';
	sufmax[N-1] = A[N-1];
	for(int i=N-2;i>=0;i--){
		sufmax[i] = max(sufmax[i+1], A[i]);
	}
	//for(int i=0;i<N;i++) cout << sufmax[i] << " ";
	for(auto i:V2){
		//debug(i);
		for(int j=0;j<i;j++){
			int grr = 2 * i - j;
			if(grr >= N || grr < 0) continue;
			ans = max(ans, A[i] + A[j] + sufmax[grr]);
			//cout << i << " " << j << " " << grr << ' ' << sufmax[grr] << '\n';
		}
		for(int j=i+1;j<N;j++){
			int grr = 2*j - i;
			if(grr < 0 || grr >= N) continue;
			ans = max(ans, A[i] + A[j] + sufmax[grr]);
		}
		multiset<int> M;
		for(int j=i-1;j>=0;j--){
			int grr = 2*j - i;
			if(grr >= 0) M.insert(A[grr]);
			if(grr >= -1) M.insert(A[grr + 1]);
			if(M.find(A[j]) != M.end()) M.erase(M.find(A[j]));
			//cout << "HEH" << endl;
			auto it = M.end();
			//cout << M.size() << endl;
			if(!M.empty()){
				//cout << "WHAT" << endl;
				it--;
				ans = max(ans, A[i] + A[j] + *(it));
				//cout << i << " " << j << " " << A[i] + A[j] + *(--M.end()) << '\n';
			}
		}
	}
	
	return ans;
	
}
main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int N;
	cin >> N;
	int A[N];
	for(int i=0;i<N;i++) cin >> A[i];
	int Q;
	cin >> Q;
	for(int i=0;i<Q;i++){
		int l,r;
		cin >> l >> r;
		l--;
		r--;
		int x = r - l + 1;
		int B[x];
		for(int i=0;i<x;i++){
			B[i] = A[i+l];
		}
		cout << getans(B, x) << '\n';
	}
	return 0;
}

Compilation message (stderr)

jumps.cpp:68:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   68 | main(){
      | ^~~~

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