Submission #413662

#	Time	Username	Problem	Language	Result	Execution time	Memory
413662		rabbitsthecat	Triple Jump (JOI19_jumps)	C++17	19 / 100	2238 ms	524292 KiB

jumps

#include "bits/stdc++.h"
using namespace std;
 
#define ffor(n) for(int i = 0; i < n; i++)
#define fffor(n) for(int j = 0; j < n; j++)
#define uwu ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize("Ofast")
 
const int INF = 1e9 + 7;
const long long INF2 = 1e17;

struct node{
	int value; 
	node() {
		value = 0;
	}
	node(int _value) {
		value = _value;
	}
};

struct segmenttree{
	int n, n2 = 1;
	vector <node> tree;
	
	// CHANGE THIS
	node merge(node p, node q) {
		return max(p.value, q.value);
	}
	
	segmenttree(vector <node>& v) {
		n = v.size();
		while(n2 < n) n2 *= 2;
		tree = vector <node>(2 * n2);
		
		for(int i = 0; i < n; i++) {
			tree[i + n2] = v[i];
		}
		for(int i = n2 - 1; i >= 1; i--) {
			tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
		}
	}
	
	void update(int pos, node value) {
		pos += n2 - 1;
		tree[pos] = value; // AND POSSIBLY THIS
		
		while(pos > 1) {
			pos /= 2;
			tree[pos] = merge(tree[2 * pos], tree[2 * pos + 1]);
		}
	}
	
	node query(int current, int a, int b, int l, int r, int node_span) {
		if (a <= l && r <= b) {
			return tree[current];
		}
		else if (a > r || l > b) {
			return node();
		}
		else {
			int child_span = node_span / 2;
			return merge(query(2 * current, a, b, l, l + child_span - 1, child_span), 
						query(2 * current + 1, a, b, l + child_span, r, child_span));
		}
	}
	
	node query(int a, int b) {
		return query(1, a, b, 1, n2, n2);
	}
};

int main(void) {
	uwu
	
	int n; cin >> n;
	vector <long long> v(n);
	ffor(n) cin >> v[i];
	
	/*
	 * let dp[i][j] -> max answer if we start at i and end at j
	 * we query the maximum in range (i + 1, (i + j) / 2)
	 */
	vector <node> temp(n);
	ffor(n) temp[i] = v[i];
	segmenttree tree(temp);
	
	vector <vector <long long>> dp(n, vector <long long>(n));
	for(int i = 0; i < n; i++) {
		for(int j = i + 2; j < n; j++) {
			int left = i + 1, right = (i + j) / 2;
			int maximum = tree.query(left + 1, right + 1).value;
			dp[i][j] = v[i] + v[j] + maximum;
		}
	}
		
	vector <vector <long long>> dp2(n, vector <long long>(n, -1));
	auto update = [&] (int left, int right, auto&& update) -> void {
		if (dp2[left][right] != -1) return;
		if (left == right) {
			dp2[left][right] = 0;
		}
		else {
			update(left + 1, right, update);
			update(left, right - 1, update);
			dp2[left][right] = max({dp[left][right], dp2[left][right - 1], dp2[left + 1][right]});
		}
	};
	
	update(0, n - 1, update);
	
	int q; cin >> q;
	ffor(q) {
		int a, b; cin >> a >> b;
		a--; b--;
		cout << dp2[a][b] << '\n';
	}
}

/*
C:\Users\kenne\OneDrive\Desktop\competitive_programming\main.cpp
*/

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