oj.uz

Submission #942719

# Submission time Handle Problem Language Result Execution time Memory
942719 2024-03-11T03:31:28 Z Tyx2019 Triple Jump (JOI19_jumps) C++17
32 / 100
 4000 ms 10440 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 = 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

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 456 KB Output is correct
2 Correct 7 ms 344 KB Output is correct
3 Correct 5 ms 344 KB Output is correct
4 Correct 4 ms 348 KB Output is correct
5 Correct 7 ms 348 KB Output is correct
6 Correct 7 ms 348 KB Output is correct
7 Correct 7 ms 460 KB Output is correct
8 Correct 7 ms 348 KB Output is correct
9 Correct 8 ms 460 KB Output is correct
10 Correct 5 ms 344 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 456 KB Output is correct
2 Correct 7 ms 344 KB Output is correct
3 Correct 5 ms 344 KB Output is correct
4 Correct 4 ms 348 KB Output is correct
5 Correct 7 ms 348 KB Output is correct
6 Correct 7 ms 348 KB Output is correct
7 Correct 7 ms 460 KB Output is correct
8 Correct 7 ms 348 KB Output is correct
9 Correct 8 ms 460 KB Output is correct
10 Correct 5 ms 344 KB Output is correct
11 Execution timed out 4019 ms 916 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1531 ms 10432 KB Output is correct
2 Correct 917 ms 10440 KB Output is correct
3 Correct 46 ms 5788 KB Output is correct
4 Correct 2420 ms 10356 KB Output is correct
5 Correct 2495 ms 10360 KB Output is correct
6 Correct 3521 ms 10072 KB Output is correct
7 Correct 2947 ms 9160 KB Output is correct
8 Correct 2984 ms 9156 KB Output is correct
9 Correct 1014 ms 9900 KB Output is correct

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 456 KB Output is correct
2 Correct 7 ms 344 KB Output is correct
3 Correct 5 ms 344 KB Output is correct
4 Correct 4 ms 348 KB Output is correct
5 Correct 7 ms 348 KB Output is correct
6 Correct 7 ms 348 KB Output is correct
7 Correct 7 ms 460 KB Output is correct
8 Correct 7 ms 348 KB Output is correct
9 Correct 8 ms 460 KB Output is correct
10 Correct 5 ms 344 KB Output is correct
11 Execution timed out 4019 ms 916 KB Time limit exceeded
12 Halted 0 ms 0 KB -