답안 #946407

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
946407	2024-03-14T16:02:49 Z	dsyz	3단 점프 (JOI19_jumps)	C++17	19 / 100	1051 ms	524288 KB

jumps

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
struct node {
	ll s,e,m,v;
	node *l, *r;
	node(ll _s,ll _e){
		s = _s;
		e = _e;
		m = (s +  e) / 2;
		v = 0;
		if(s != e){
			l = new node(s,m);
			r = new node(m + 1,e);
		}
	}
	void update(ll x,ll nval){
		if(s == e){
			v = nval;
			return;
		}else{
			if(x > m) r -> update(x,nval);
			else l -> update(x,nval);
			v = max(l -> v,r -> v);
		}
	}
	ll rmq(ll x,ll y){
		if(s == x && e == y){
			return v;
		}else{
			if(x > m) return r -> rmq(x,y);
			else if(y <= m) return l -> rmq(x,y);
			else return max(l -> rmq(x,m),r -> rmq(m + 1,y));
		}
	}
} *root;
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N;
	cin>>N;
	root = new node(0,N - 1);
	ll arr[N];
	for(ll i = 0;i < N;i++){
		cin>>arr[i];
		root -> update(i,arr[i]);
	}
	ll dp[N][N];
	memset(dp,0,sizeof(dp));
	for(ll l = N - 3;l >= 0;l--){
		for(ll r = l + 2;r < N;r++){
			dp[l][r] = max({arr[l] + root -> rmq(l + 1,(l + r) / 2) + arr[r],dp[l][r - 1],dp[l + 1][r]});
		}
	}
	ll Q;
	cin>>Q;
	for(ll q = 0;q < Q;q++){
		ll l,r;
		cin>>l>>r;
		l--, r--;
		cout<<dp[l][r]<<'\n';
	}
}

Subtask #1

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	600 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	600 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	400 KB	Output is correct
7	Correct	1 ms	344 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct

Subtask #2

14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	600 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	600 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	400 KB	Output is correct
7	Correct	1 ms	344 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	1051 ms	204332 KB	Output is correct
12	Correct	1016 ms	204116 KB	Output is correct
13	Correct	1026 ms	204204 KB	Output is correct
14	Correct	1029 ms	204368 KB	Output is correct
15	Correct	1024 ms	204316 KB	Output is correct
16	Correct	1029 ms	203860 KB	Output is correct
17	Correct	1020 ms	203672 KB	Output is correct
18	Correct	1014 ms	203600 KB	Output is correct
19	Correct	1024 ms	204112 KB	Output is correct

Subtask #3

0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	400 ms	524288 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #4

0 / 54.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	600 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	600 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	400 KB	Output is correct
7	Correct	1 ms	344 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	1051 ms	204332 KB	Output is correct
12	Correct	1016 ms	204116 KB	Output is correct
13	Correct	1026 ms	204204 KB	Output is correct
14	Correct	1029 ms	204368 KB	Output is correct
15	Correct	1024 ms	204316 KB	Output is correct
16	Correct	1029 ms	203860 KB	Output is correct
17	Correct	1020 ms	203672 KB	Output is correct
18	Correct	1014 ms	203600 KB	Output is correct
19	Correct	1024 ms	204112 KB	Output is correct
20	Runtime error	400 ms	524288 KB	Execution killed with signal 9
21	Halted	0 ms	0 KB	-