oj.uz

Submission #1096485

# Submission time Handle Problem Language Result Execution time Memory
1096485 2024-10-04T15:12:23 Z letritien Triple Jump (JOI19_jumps) C++17
19 / 100
 1337 ms 407684 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 791 ms 127140 KB Output is correct
12 Correct 854 ms 126992 KB Output is correct
13 Correct 776 ms 127056 KB Output is correct
14 Correct 814 ms 126988 KB Output is correct
15 Correct 786 ms 127060 KB Output is correct
16 Correct 821 ms 126292 KB Output is correct
17 Correct 846 ms 126292 KB Output is correct
18 Correct 804 ms 126280 KB Output is correct
19 Correct 810 ms 126808 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 1337 ms 407684 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 791 ms 127140 KB Output is correct
12 Correct 854 ms 126992 KB Output is correct
13 Correct 776 ms 127056 KB Output is correct
14 Correct 814 ms 126988 KB Output is correct
15 Correct 786 ms 127060 KB Output is correct
16 Correct 821 ms 126292 KB Output is correct
17 Correct 846 ms 126292 KB Output is correct
18 Correct 804 ms 126280 KB Output is correct
19 Correct 810 ms 126808 KB Output is correct
20 Runtime error 1337 ms 407684 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -