Submission #1139940

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139940		SmuggingSpun	Triple Jump (JOI19_jumps)	C++20	5 / 100	420 ms	201556 KiB

jumps

#include<bits/stdc++.h>
#define taskname "A"
using namespace std;
const int lim = 5e5 + 5;
template<class T>void maximize(T& a, T b){
	if(a < b){
		a = b;
	}
}
int n, q, a[lim];
namespace sub1{
	void solve(){
		for(int _ = 0; _ < q; _++){
			int l, r, ans = 0;
			cin >> l >> r;
			for(int i = l; i < r; i++){
				for(int j = i + 1; j < r; j++){
					for(int k = r; k > j; k--){
						if(k - j < j - i){
							break;
						}
						maximize(ans, a[i] + a[j] + a[k]);
					}
				}
			}
			cout << ans << "\n";
		}
	}
}
namespace sub2{
	void solve(){
		vector<vector<int>>range_max(n + 1, vector<int>(n + 1)), dp(n + 1, vector<int>(n + 1));
		for(int i = 1; i <= n; i++){
			range_max[i][i] = i;
			for(int j = i + 1; j <= n; j++){
				range_max[i][j] = max(range_max[i][j - 1], a[j]);
			}
		}
		for(int i = n; i > 2; i--){
			dp[i - 2][i] = a[i] + a[i - 1] + a[i - 2];
		}
		for(int len = 3; len < n; len++){
			for(int r = n; r > len; r--){
				int l = r - len;
				dp[l][r] = max(max(dp[l][r - 1], dp[l + 1][r]), a[l] + a[r] + range_max[l + 1][l + (len >> 1)]);
			}
		}
		for(int _ = 0; _ < q; _++){
			int l, r;
			cin >> l >> r;
			cout << dp[l][r] << "\n";
		}
	}
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	cin >> q;
	if(n <= 100 && q <= 100){
		sub1::solve();
	}
	else if(n <= 5000){
		sub2::solve();
	}
}

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:58:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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