oj.uz

Submission #135535

# Submission time Handle Problem Language Result Execution time Memory
135535 2019-07-24T07:49:17 Z KLPP Triple Jump (JOI19_jumps) C++14
19 / 100
 2625 ms 451112 KB 
#include<bits/stdc++.h>

using namespace std;
typedef long long int lld;
#define rep(i,a,b) for(int i=a;i<b;i++)
lld SG[5000][5000];
bool visited[5000][5000];
lld compute(int i, int j){
  if(visited[i][j])return SG[i][j];
  SG[i][j]=max(SG[i][j],compute(i+1,j));
  SG[i][j]=max(SG[i][j],compute(i,j-1));
  visited[i][j]=true;
  return SG[i][j];
}
int main(){
  int n,q;
  scanf("%d",&n);
  lld arr[n];
  rep(i,0,n)scanf("%lld",&arr[i]);
  
  scanf("%d",&q);
  rep(i,0,n){
    rep(j,0,n)SG[i][j]=0,visited[i][j]=false;
  }
  rep(i,0,n-2){
    visited[i][i+2]=true;
  }
  rep(i,0,n){
    lld B=arr[i+1];
    rep(j,i+2,n){
      B=max(B,arr[(i+j)/2]);
      SG[i][j]=max(SG[i][j],arr[i]+B+arr[j]);
    }
  }
  while(q--){
    int x,y;
    scanf("%d %d",&x,&y);
    x--;y--;
    printf("%lld\n",compute(x,y));
  }
  return 0;
}

Compilation message

jumps.cpp: In function 'int main()':
jumps.cpp:17:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
   ~~~~~^~~~~~~~~
jumps.cpp:19:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   rep(i,0,n)scanf("%lld",&arr[i]);
             ~~~~~^~~~~~~~~~~~~~~~
jumps.cpp:21:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&q);
   ~~~~~^~~~~~~~~
jumps.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&x,&y);
     ~~~~~^~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 3 ms 1272 KB Output is correct
3 Correct 3 ms 1272 KB Output is correct
4 Correct 3 ms 1272 KB Output is correct
5 Correct 3 ms 1144 KB Output is correct
6 Correct 3 ms 1144 KB Output is correct
7 Correct 3 ms 1144 KB Output is correct
8 Correct 3 ms 1144 KB Output is correct
9 Correct 3 ms 1272 KB Output is correct
10 Correct 3 ms 1144 KB Output is correct
11 Correct 594 ms 230584 KB Output is correct
12 Correct 597 ms 230648 KB Output is correct
13 Correct 607 ms 230348 KB Output is correct
14 Correct 592 ms 230520 KB Output is correct
15 Correct 605 ms 230424 KB Output is correct
16 Correct 603 ms 229824 KB Output is correct
17 Correct 598 ms 229784 KB Output is correct
18 Correct 601 ms 229724 KB Output is correct
19 Correct 600 ms 230392 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 2625 ms 451112 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 3 ms 1272 KB Output is correct
3 Correct 3 ms 1272 KB Output is correct
4 Correct 3 ms 1272 KB Output is correct
5 Correct 3 ms 1144 KB Output is correct
6 Correct 3 ms 1144 KB Output is correct
7 Correct 3 ms 1144 KB Output is correct
8 Correct 3 ms 1144 KB Output is correct
9 Correct 3 ms 1272 KB Output is correct
10 Correct 3 ms 1144 KB Output is correct
11 Correct 594 ms 230584 KB Output is correct
12 Correct 597 ms 230648 KB Output is correct
13 Correct 607 ms 230348 KB Output is correct
14 Correct 592 ms 230520 KB Output is correct
15 Correct 605 ms 230424 KB Output is correct
16 Correct 603 ms 229824 KB Output is correct
17 Correct 598 ms 229784 KB Output is correct
18 Correct 601 ms 229724 KB Output is correct
19 Correct 600 ms 230392 KB Output is correct
20 Runtime error 2625 ms 451112 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -