oj.uz

답안 #242235

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
242235 2020-06-27T07:10:58 Z dwsc 3단 점프 (JOI19_jumps) C++14
19 / 100
 4000 ms 276252 KB 
#include <bits/stdc++.h>
using namespace std;
int memo[5010][5010];
int arr[5010];
int pre[5010][5010];
int n,q;
int dp(int i,int j){
    if (i+2 > j) return 0;
    if (memo[i][j] != -1) return memo[i][j];
    int dist = (j-i)/2;
    int maxi = pre[i+1][i+dist];
    return memo[i][j] = max(arr[i]+arr[j]+maxi,max(dp(i+1,j),dp(i,j-1)));
}
int main(){
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> arr[i];
    for (int i = 1; i <= n; i++){
        for (int j = i; j <= n; j++){
            pre[i][j] = max(pre[i][j-1],arr[j]);
            memo[i][j] = -1;
        }
    }
    cin >> q;
    for (int i = 0; i < q; i++){
        int l,r;
        cin >> l >> r;
        cout << dp(l,r) << "\n";
    }
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 1152 KB Output is correct
3 Correct 6 ms 1152 KB Output is correct
4 Correct 5 ms 1152 KB Output is correct
5 Correct 5 ms 1152 KB Output is correct
6 Correct 6 ms 1152 KB Output is correct
7 Correct 5 ms 1152 KB Output is correct
8 Correct 6 ms 1152 KB Output is correct
9 Correct 5 ms 1152 KB Output is correct
10 Correct 5 ms 1152 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 1152 KB Output is correct
3 Correct 6 ms 1152 KB Output is correct
4 Correct 5 ms 1152 KB Output is correct
5 Correct 5 ms 1152 KB Output is correct
6 Correct 6 ms 1152 KB Output is correct
7 Correct 5 ms 1152 KB Output is correct
8 Correct 6 ms 1152 KB Output is correct
9 Correct 5 ms 1152 KB Output is correct
10 Correct 5 ms 1152 KB Output is correct
11 Correct 1975 ms 140000 KB Output is correct
12 Correct 1996 ms 140024 KB Output is correct
13 Correct 1896 ms 139896 KB Output is correct
14 Correct 1987 ms 140152 KB Output is correct
15 Correct 1971 ms 139896 KB Output is correct
16 Correct 1937 ms 139384 KB Output is correct
17 Correct 1872 ms 139256 KB Output is correct
18 Correct 1896 ms 139336 KB Output is correct
19 Correct 1946 ms 139896 KB Output is correct

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4083 ms 276252 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 1152 KB Output is correct
3 Correct 6 ms 1152 KB Output is correct
4 Correct 5 ms 1152 KB Output is correct
5 Correct 5 ms 1152 KB Output is correct
6 Correct 6 ms 1152 KB Output is correct
7 Correct 5 ms 1152 KB Output is correct
8 Correct 6 ms 1152 KB Output is correct
9 Correct 5 ms 1152 KB Output is correct
10 Correct 5 ms 1152 KB Output is correct
11 Correct 1975 ms 140000 KB Output is correct
12 Correct 1996 ms 140024 KB Output is correct
13 Correct 1896 ms 139896 KB Output is correct
14 Correct 1987 ms 140152 KB Output is correct
15 Correct 1971 ms 139896 KB Output is correct
16 Correct 1937 ms 139384 KB Output is correct
17 Correct 1872 ms 139256 KB Output is correct
18 Correct 1896 ms 139336 KB Output is correct
19 Correct 1946 ms 139896 KB Output is correct
20 Execution timed out 4083 ms 276252 KB Time limit exceeded
21 Halted 0 ms 0 KB -