Submission #1096485

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096485		letritien	Triple Jump (JOI19_jumps)	C++17	19 / 100	1337 ms	407684 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5 + 5;
int  n, query;
int a[N];

void subtask1(){
	while(query--){
		int l, r; cin >> l >> r;
		int ans = -5e5;
		for(int i = l; i <= r; i++){
			for(int j = i + 1; j <= r; j++){
				for(int k = j + 1; k <= r; k++){
					int val = a[i] + a[j] + a[k];
					if(j - i <= k - j) ans = max(ans, val);
				}
			}
		}
		cout << ans << endl;
	}
}
void subtask3(){
	while(query--){
		int l, r; cin >> l >> r;
		if(r + 1 - l == 3) cout << a[l] + a[l + 1] + a[r] << endl;
		else{
			int xyz = -5e5, _z = -5e5, xy_z = -5e5, pos = 0;
			for(int i = l; i <= r; i++){
				int val = a[i] + a[i + 1] + a[i + 2];
				if(i == r - 2) break;
				xyz = max(xyz, val);
			}
			for(int i = l; i <= r; i++){
				int val = a[i] + a[i + 1];
				if(i == r - 1) break;
				(val >= xy_z) ? xy_z = val, pos = i + 1 : 1;
			} 
			for(int i = pos + 1; i <= r; i++){
				_z = max(_z, a[i]);
			}
			cout << max(xyz, xy_z + _z) << endl;
		}
	}
}
long long dp[5005][5005];
void subtask2(){
    for (int i = 1; i <= n - 2; ++i){
        int Max = 0;
        for (int j = i + 2; j <= n; ++j){
            Max = max(Max, a[(i + j) / 2]);
            dp[i][j] = a[i] + Max + a[j];
        }
	}
    for(int len = 4; len <= n; ++len){
        for (int l = 1; l <= n - len + 1; ++l){
            int r = l + len - 1;
            dp[l][r] = max(dp[l][r], max(dp[l + 1][r], dp[l][r - 1]));
        }
    }
    while (query--){
        int l, r; cin >> l >> r;
        cout << dp[l][r] << endl;
    }
}
signed main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	cin >> query;
	if(n <= 100 && query <= 100) subtask1();
	else if(100 < n <= 5000) subtask2();
	else subtask3();
}

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:73:18: warning: comparison of constant '5000' with boolean expression is always true [-Wbool-compare]
   73 |  else if(100 < n <= 5000) subtask2();
      |          ~~~~~~~~^~~~~~~
jumps.cpp:73:14: warning: comparisons like 'X<=Y<=Z' do not have their mathematical meaning [-Wparentheses]
   73 |  else if(100 < n <= 5000) subtask2();
      |          ~~~~^~~

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