oj.uz

Submission #138059

# Submission time Handle Problem Language Result Execution time Memory
138059 2019-07-29T08:31:03 Z MrTEK Triple Jump (JOI19_jumps) C++14
0 / 100
 33 ms 3620 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Runtime error 3 ms 508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Runtime error 3 ms 508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 3620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Runtime error 3 ms 508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -