Submission #1139999

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139999		SmuggingSpun	Triple Jump (JOI19_jumps)	C++20	46 / 100	434 ms	201552 KiB

jumps

#include<bits/stdc++.h>
#define taskname "A"
using namespace std;
const int lim = 5e5 + 5;
const int INF = 1e9;
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] = a[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";
		}
	}
}
namespace sub3{
	const int lim = 2e5 + 5;
	int log_v[lim], spt[lim][18];
	int get_max(int l, int r){
		if(l > r){
			return -1;
		}
		int k = log_v[r - l + 1];
		return max(spt[l][k], spt[r - (1 << k) + 1][k]);
	}
	void solve(){
		log_v[0] = -1;
		for(int i = 1; i <= n; i++){
			log_v[i] = log_v[i >> 1] + 1;
			spt[i][0] = a[i];
		}
		for(int j = 1; j < 18; j++){
			for(int i = 1; i + (1 << j) - 1 <= n; i++){
				spt[i][j] = max(spt[i][j - 1], spt[i + (1 << (j - 1))][j - 1]);
			}
		}
		vector<int>right_max(n + 1);
		stack<int>st;
		for(int i = n; i > 0; st.push(i--)){
			while(!st.empty() && a[st.top()] < a[i]){
				st.pop();
			}
			right_max[i] = (st.empty() ? -1 : st.top());
		}
		int l, r, ans = 0;
		cin >> l >> r;
		vector<int>suf(n + 2, -INF);
		for(int i = r; i >= l; i--){
			suf[i] = max(suf[i + 1], a[i]);
		}
		for(int i = l; i < r; i++){
			int x = i + 1;
			while(true){
				int T = (x << 1) - i;
				if(T > r){
					break;
				}
				maximize(ans, a[i] + a[x] + suf[T]);
				if(get_max(i + 1, x - 1) >= a[i]){
					break;
				}
				if((x = right_max[x]) == -1){
					break;
				}
			}
		}
		cout << ans << "\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();
	}
	else if(n <= 200000 && q == 1){
		sub3::solve();
	}
}

Compilation message (stderr)

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

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