oj.uz

답안 #1096485

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1096485 2024-10-04T15:12:23 Z letritien 3단 점프 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -