제출 #946407

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
946407		dsyz	Triple Jump (JOI19_jumps)	C++17	19 / 100	1051 ms	524288 KiB

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 / 5
• Subtask 2: 14 / 14
• Subtask 3: 0 / 27
• Subtask 4: 0 / 54