oj.uz

Submission #810503

# Submission time Handle Problem Language Result Execution time Memory
810503 2023-08-06T10:31:31 Z rnl42 Triple Jump (JOI19_jumps) C++14
19 / 100
 386 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
	bool first = true;
	string res = "[";
	for (const auto &x : v) {
		if (!first)
			res += ", ";
		first = false;
		res += to_string(x);
	}
	res += "]";
	return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
	cout << ' ' << to_string(H);
	dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

int N, Q;
vector<int> A;

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> N;
	A.resize(N);
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	vector<vector<int>> bestmid(N, vector<int>(N, -1));
	vector<vector<int>> dp(N, vector<int>(N, -1));
	for (int l = 0; l < N; l++) {
		pair<int,int> maxi(-1e9, -1e9);
		for (int r = l+1; r < N; r++) {
			if (!((l-r)&1)) {
				maxi = max(maxi, make_pair(A[(l+r)>>1], (l+r)>>1));
			}
			if (l+2 <= r) {
				bestmid[l][r] = maxi.second;
				dp[l][r] = max(dp[l][r], A[l]+A[r]+maxi.first);
				dbg(l, r, dp[l][r]);
			}
		}
	}
	for (int l = N-1; l >= 0; l--) {
		for (int r = l+2; r < N; r++) {
			dp[l][r] = max(dp[l][r], max(dp[l][r-1], dp[l+1][r]));
		}
	}
	cin >> Q;
	int l, r;
	for (int i = 0; i < Q; i++) {
		cin >> l >> r, l--, r--;
		cout << dp[l][r] << '\n';
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 320 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 320 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 307 ms 206224 KB Output is correct
12 Correct 312 ms 206112 KB Output is correct
13 Correct 303 ms 206032 KB Output is correct
14 Correct 386 ms 206160 KB Output is correct
15 Correct 310 ms 206112 KB Output is correct
16 Correct 318 ms 205376 KB Output is correct
17 Correct 300 ms 205384 KB Output is correct
18 Correct 320 ms 205456 KB Output is correct
19 Correct 306 ms 205960 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 197 ms 524288 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 320 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 320 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 307 ms 206224 KB Output is correct
12 Correct 312 ms 206112 KB Output is correct
13 Correct 303 ms 206032 KB Output is correct
14 Correct 386 ms 206160 KB Output is correct
15 Correct 310 ms 206112 KB Output is correct
16 Correct 318 ms 205376 KB Output is correct
17 Correct 300 ms 205384 KB Output is correct
18 Correct 320 ms 205456 KB Output is correct
19 Correct 306 ms 205960 KB Output is correct
20 Runtime error 197 ms 524288 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -