Submission #941002

#	Time	Username	Problem	Language	Result	Execution time	Memory
941002		shoryu386	Triple Jump (JOI19_jumps)	C++17	19 / 100	1159 ms	403480 KiB

jumps

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define sz(x) ((int)x.size())

#define MAX 5007
int denseTable[MAX][MAX];
main(){ ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	int arr[n]; for (int x = 0; x < n; x++) cin >> arr[x];
	
	for (int x = 0; x < n; x++){
		
		int carry = arr[x];
		for (int y = x; y < n; y++){
			carry = max(arr[y], carry);
			denseTable[x][y] = carry;
		}
	}
	
	int results[n][n]; memset(results, 0, sizeof(results));
	for (int a = 0; a < n; a++){
		for (int c = a+2; c < n; c++){
			int endpt = (a+c)/2;
			results[a][c] = arr[a] + arr[c] + denseTable[a+1][endpt];
		}
	}
	
	for (int sz = 1; sz <= n; sz++){
		for (int x = 0; x+sz-1 < n; x++){
			if (x+sz < n) results[x][x+sz] = max(results[x][x+sz], results[x][x+sz-1]);
			if (x != 0) results[x-1][x+sz-1] = max(results[x-1][x+sz-1], results[x][x+sz-1]);
		}
	}
	
	int q; cin >> q;
	for (int x = 0; x < q; x++){
		int ql, qr; cin >> ql >> qr; ql--; qr--;
		cout << results[ql][qr] << '\n';
	}
}

Compilation message (stderr)

jumps.cpp:9:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    9 | main(){ ios_base::sync_with_stdio(0); cin.tie(0);
      | ^~~~

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