oj.uz

답안 #402507

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
402507 2021-05-11T21:07:45 Z AmineWeslati 3단 점프 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -