oj.uz

Submission #402560

# Submission time Handle Problem Language Result Execution time Memory
402560 2021-05-12T00:34:22 Z AmineWeslati Triple Jump (JOI19_jumps) C++14
27 / 100
 1164 ms 6236 KB 
#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 all(x) begin(x),end(x)

#define dbgv(v) for(auto x: v) cerr << x << ' '; cerr << endl;

#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--)

const int nx[4]={-1,0,1,0},ny[4]={0,1,0,-1};

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=2e5+10;

int N;
vi a(MX);

bool cmp(int i, int j){
	return a[i]>a[j];
}

vi t(MX*4);
void build(int pos=1, int l=0, int r=N-1){
	if(l==r){
		t[pos]=a[l];
		return; 
	}

	int m=(l+r)/2;
	build(pos*2,l,m);
	build(pos*2+1,m+1,r);
	t[pos]=max(t[pos*2],t[pos*2+1]);
}

int get(int l, int r, int pos=1, int tl=0, int tr=N-1){
	if(l>r) return -1e9;
	if(l==tl && r==tr) return t[pos];

	int tm=(tl+tr)/2;
	return max(get(l,min(r,tm),pos*2,tl,tm),
		get(max(l,tm+1),r,pos*2+1,tm+1,tr));
}

int main(){
	IO();

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

	build();

	vi vec(N); iota(all(vec),0);
	sort(all(vec),cmp);

	int Q; cin>>Q>>Q>>Q;

	const int B=20;
	int ans=0;
	FOR(idx,0,min(sz(vec),B)){
		int i=vec[idx];

		//left
		FOR(j,i+1,N){
			ckmax(ans,a[i]+a[j]+get(2*j-i,N-1));
		}


		//mid

		FOR(j,0,i){
			ckmax(ans,a[i]+a[j]+get(2*i-j,N-1));
		}

		//right

		FOR(j,0,i){
			ckmax(ans,a[i]+a[j]+get(max(0,2*j-i),j-1));
		}
	}

	cout << ans << endl;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4172 KB Output is correct
2 Incorrect 3 ms 4172 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4172 KB Output is correct
2 Incorrect 3 ms 4172 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 963 ms 4984 KB Output is correct
2 Correct 1164 ms 5060 KB Output is correct
3 Correct 495 ms 4984 KB Output is correct
4 Correct 1129 ms 4988 KB Output is correct
5 Correct 1152 ms 4984 KB Output is correct
6 Correct 1160 ms 6064 KB Output is correct
7 Correct 1161 ms 5992 KB Output is correct
8 Correct 1161 ms 6088 KB Output is correct
9 Correct 885 ms 6236 KB Output is correct

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4172 KB Output is correct
2 Incorrect 3 ms 4172 KB Output isn't correct
3 Halted 0 ms 0 KB -