Submission #156101

#	Time	Username	Problem	Language	Result	Execution time	Memory
156101		kostia244	Triple Jump (JOI19_jumps)	C++14	19 / 100	859 ms	412240 KiB

jumps

#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define pb push_back
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using vi = vector<ll>;
using vvi = vector<vi>;
const ll mod = 1000000007ll;
ll n, mx[5050][5050], dp[5050][5050];
vi a;

ll getmax(int l, int r) {
	l = max(l, 1);
	r = min(r, (int)n);
	if(l > r) return 0;
	if(mx[l][r]) return mx[l][r];
	if(l == r) return mx[l][r] = a[l];
	return mx[l][r] = max(getmax(l, r-1),  a[r]);
}

ll get(int l, int r) {
	if(r-l<2) return 0;
	if(dp[l][r] != -1) return dp[l][r];
	dp[l][r] = a[l]+a[r]+getmax(l+1, (r+l)/2);
	dp[l][r] = max({dp[l][r], get(l+1, r), get(l, r-1)});
	return dp[l][r];
}

int main() {
	ios::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);
	memset(dp, -1, sizeof dp);
	memset(mx, 0, sizeof mx);
	cin >> n;
	a.resize(n+1);
	for(int i = 1; i <= n; i++) cin >> a[i];
	int q, l, r;
	cin >> q;
	while(q--) {
		cin >> l >> r;
		cout << get(l, r) << "\n";
	}
	
}

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