oj.uz

Submission #413662

# Submission time Handle Problem Language Result Execution time Memory
413662 2021-05-29T08:26:37 Z rabbitsthecat Triple Jump (JOI19_jumps) C++17
19 / 100
 2238 ms 524292 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 440 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 440 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 2209 ms 402276 KB Output is correct
12 Correct 2238 ms 402036 KB Output is correct
13 Correct 2165 ms 402152 KB Output is correct
14 Correct 2161 ms 402208 KB Output is correct
15 Correct 2141 ms 402312 KB Output is correct
16 Correct 2191 ms 401512 KB Output is correct
17 Correct 2139 ms 401424 KB Output is correct
18 Correct 2192 ms 401508 KB Output is correct
19 Correct 2180 ms 402028 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 291 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 440 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 2209 ms 402276 KB Output is correct
12 Correct 2238 ms 402036 KB Output is correct
13 Correct 2165 ms 402152 KB Output is correct
14 Correct 2161 ms 402208 KB Output is correct
15 Correct 2141 ms 402312 KB Output is correct
16 Correct 2191 ms 401512 KB Output is correct
17 Correct 2139 ms 401424 KB Output is correct
18 Correct 2192 ms 401508 KB Output is correct
19 Correct 2180 ms 402028 KB Output is correct
20 Runtime error 291 ms 524292 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -