Submission #810503

#	Time	Username	Problem	Language	Result	Execution time	Memory
810503		rnl42	Triple Jump (JOI19_jumps)	C++14	19 / 100	386 ms	524288 KiB

jumps

#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 / 5
• Subtask 2: 14 / 14
• Subtask 3: 0 / 27
• Subtask 4: 0 / 54