oj.uz

Submission #402507

# Submission time Handle Problem Language Result Execution time Memory
402507 2021-05-11T21:07:45 Z AmineWeslati Triple Jump (JOI19_jumps) C++14
19 / 100
 3508 ms 137404 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 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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 716 KB Output is correct
3 Correct 2 ms 716 KB Output is correct
4 Correct 2 ms 716 KB Output is correct
5 Correct 2 ms 704 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 2 ms 716 KB Output is correct
8 Correct 2 ms 716 KB Output is correct
9 Correct 2 ms 716 KB Output is correct
10 Correct 2 ms 704 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 716 KB Output is correct
3 Correct 2 ms 716 KB Output is correct
4 Correct 2 ms 716 KB Output is correct
5 Correct 2 ms 704 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 2 ms 716 KB Output is correct
8 Correct 2 ms 716 KB Output is correct
9 Correct 2 ms 716 KB Output is correct
10 Correct 2 ms 704 KB Output is correct
11 Correct 3495 ms 77100 KB Output is correct
12 Correct 2864 ms 77168 KB Output is correct
13 Correct 2821 ms 77140 KB Output is correct
14 Correct 3444 ms 77100 KB Output is correct
15 Correct 3508 ms 77036 KB Output is correct
16 Correct 3460 ms 76368 KB Output is correct
17 Correct 3484 ms 76540 KB Output is correct
18 Correct 3485 ms 76588 KB Output is correct
19 Correct 3428 ms 76984 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 2295 ms 137404 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 716 KB Output is correct
3 Correct 2 ms 716 KB Output is correct
4 Correct 2 ms 716 KB Output is correct
5 Correct 2 ms 704 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 2 ms 716 KB Output is correct
8 Correct 2 ms 716 KB Output is correct
9 Correct 2 ms 716 KB Output is correct
10 Correct 2 ms 704 KB Output is correct
11 Correct 3495 ms 77100 KB Output is correct
12 Correct 2864 ms 77168 KB Output is correct
13 Correct 2821 ms 77140 KB Output is correct
14 Correct 3444 ms 77100 KB Output is correct
15 Correct 3508 ms 77036 KB Output is correct
16 Correct 3460 ms 76368 KB Output is correct
17 Correct 3484 ms 76540 KB Output is correct
18 Correct 3485 ms 76588 KB Output is correct
19 Correct 3428 ms 76984 KB Output is correct
20 Runtime error 2295 ms 137404 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -