oj.uz

Submission #942701

# Submission time Handle Problem Language Result Execution time Memory
942701 2024-03-11T03:11:04 Z Tyx2019 Triple Jump (JOI19_jumps) C++17
0 / 100
 35 ms 4428 KB 
#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 = 20;
	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) continue;
			ans = max(ans, A[i] + A[j] + sufmax[grr]);
			//cout << i << " " << j << " " << grr << ' ' << sufmax[grr] << '\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';
	}
}

Compilation message

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Incorrect 1 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Incorrect 1 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 4428 KB Output is correct
2 Correct 22 ms 4308 KB Output is correct
3 Correct 21 ms 4304 KB Output is correct
4 Correct 35 ms 4300 KB Output is correct
5 Correct 35 ms 4300 KB Output is correct
6 Incorrect 34 ms 4296 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Incorrect 1 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -