제출 #138059

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
138059		MrTEK	3단 점프 (JOI19_jumps)	C++14	0 / 100	33 ms	3620 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
 
typedef long long int ll;
typedef pair <int,int> ii;
 
const int N = 2e5 + 5;
const int inf = 2e9;
const int SQ = 300;

int n,q,a[N],suff[N];
ll ans;

void f(int l,int r,int optl,int optr) {
	if (l > r)
		return;
	int mid = (l + r) / 2;
	int newopt = mid - 1;
	ll val = 0;
	for (int i = min(mid - 1,optr) ; i >= optl ; i--) {
		if (2 * mid - i > n)
			break;
		if ((ll)a[mid] + a[i] + suff[2 * mid - i] >= val) {
			val = (ll)a[mid] + a[i] + suff[2 * mid - i];
			newopt = i;
			ans = max(ans,val);
		}
	}
	// cerr << mid << " " << newopt << endl;
	f(l,mid - 1,newopt,optr);
	f(mid + 1,r,optl,newopt);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL) ; cout.tie(NULL);
	cin >> n;
	for (int i = 1 ; i <= n ; i++)
		cin >> a[i];
	cin >> q;
	assert(q == 1);
	while(q--) {
		int l,r;
		cin >> l >> r;
		assert(l == 1);
		assert(r == n);
	}
	for (int i = n ; i >= 1 ; i--)
		suff[i] = max(suff[i + 1],a[i]);
	f(2,n,1,n);
	cout << ans << endl;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 27
• Subtask 4: 0 / 54