oj.uz

Submission #515477

# Submission time Handle Problem Language Result Execution time Memory
515477 2022-01-19T08:02:11 Z 79brue Triple Jump (JOI19_jumps) C++14
19 / 100
 2359 ms 401440 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, q;
int arr[500002];
int DP[5002][5002];
int DPmax[5002][5002];

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", &arr[i]);
    for(int i=1; i<=n; i++){
        DPmax[i][i] = arr[i];
        for(int j=i+1; j<=n; j++){
            DPmax[i][j] = max(DPmax[i][j-1], arr[j]);
        }
    }
    for(int i=1; i<=n-2; i++) DP[i][i+2] = arr[i] + arr[i+1] + arr[i+2];
    for(int d=3; d<n; d++){
        for(int i=1; i+d<=n; i++){
            int j = i+d;
            DP[i][j] = max({DP[i][j-1], DP[i+1][j], arr[i] + arr[j] + DPmax[i+1][(i+j)/2]});
        }
    }

    scanf("%d", &q);
    while(q--){
        int l, r;
        scanf("%d %d", &l, &r);
        printf("%d\n", DP[l][r]);
    }
}

Compilation message

jumps.cpp: In function 'int main()':
jumps.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
jumps.cpp:14:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     for(int i=1; i<=n; i++) scanf("%d", &arr[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~
jumps.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
jumps.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         scanf("%d %d", &l, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 1 ms 1100 KB Output is correct
4 Correct 1 ms 1100 KB Output is correct
5 Correct 1 ms 1100 KB Output is correct
6 Correct 1 ms 1100 KB Output is correct
7 Correct 1 ms 1100 KB Output is correct
8 Correct 1 ms 1100 KB Output is correct
9 Correct 1 ms 1100 KB Output is correct
10 Correct 1 ms 1100 KB Output is correct
11 Correct 508 ms 139148 KB Output is correct
12 Correct 452 ms 139388 KB Output is correct
13 Correct 471 ms 139112 KB Output is correct
14 Correct 439 ms 139176 KB Output is correct
15 Correct 508 ms 139352 KB Output is correct
16 Correct 474 ms 138524 KB Output is correct
17 Correct 446 ms 138552 KB Output is correct
18 Correct 455 ms 138468 KB Output is correct
19 Correct 464 ms 139136 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 2359 ms 401440 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 0 ms 204 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 1 ms 1100 KB Output is correct
4 Correct 1 ms 1100 KB Output is correct
5 Correct 1 ms 1100 KB Output is correct
6 Correct 1 ms 1100 KB Output is correct
7 Correct 1 ms 1100 KB Output is correct
8 Correct 1 ms 1100 KB Output is correct
9 Correct 1 ms 1100 KB Output is correct
10 Correct 1 ms 1100 KB Output is correct
11 Correct 508 ms 139148 KB Output is correct
12 Correct 452 ms 139388 KB Output is correct
13 Correct 471 ms 139112 KB Output is correct
14 Correct 439 ms 139176 KB Output is correct
15 Correct 508 ms 139352 KB Output is correct
16 Correct 474 ms 138524 KB Output is correct
17 Correct 446 ms 138552 KB Output is correct
18 Correct 455 ms 138468 KB Output is correct
19 Correct 464 ms 139136 KB Output is correct
20 Runtime error 2359 ms 401440 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -