oj.uz

Submission #1013020

# Submission time Handle Problem Language Result Execution time Memory
1013020 2024-07-03T05:36:29 Z feev1x Triple Jump (JOI19_jumps) C++17
19 / 100
 272 ms 524288 KB 
/**
 *    author:  feev1x
 *    created: 03.07.2024 09:20:35
**/
#include "bits/stdc++.h"   
using namespace std;

#ifdef LOCAL
#include "C:/Algos/debug.h" 
#else
#define debug(...)  
#endif
#define int int64_t         
                     

const int N = 5e5 + 5;

int st[21][N];
int lg[N + 1];
         
int f(int l, int r) {
  int i = lg[r - l + 1];
  return max(st[i][l], st[i][r - (1 << i) + 1]);
}

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0); 
  int n; cin >> n;
  vector<int> a(n);
  for (auto &u: a) cin >> u;       
  for (int i = 0; i < n; ++i) st[0][i] = a[i];
  lg[1] = 0;
  for (int i = 2; i <= N; ++i) lg[i] = lg[i / 2] + 1;
  for (int i = 1; i <= 20; ++i)
    for (int j = 0; j + (1 << i) <= n; ++j)
      st[i][j] = max(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
  int q; cin >> q;
  vector<vector<int>> ans(n, vector<int>(n));
  for (int l = n - 3; l >= 0; --l) {
    for (int r = l + 2; r < n; ++r) {
      if (r - l + 1 == 3) {
        ans[l][r] = a[l] + a[l + 1] + a[l + 2];
      } else {
        ans[l][r] = max({ans[l + 1][r], a[l] + f(l + 1, l + (r - l) / 2) + a[r], ans[l][r - 1]});
      }
    }
  }
  while (q--) {
    int l, r; cin >> l >> r; l--, r--;
    assert(r - l + 1 >= 3);
    cout << ans[l][r] << '\n';
  }  
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7000 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 1 ms 6860 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 2 ms 4444 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7000 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 1 ms 6860 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 2 ms 4444 KB Output is correct
11 Correct 253 ms 209724 KB Output is correct
12 Correct 272 ms 209504 KB Output is correct
13 Correct 262 ms 212004 KB Output is correct
14 Correct 247 ms 212052 KB Output is correct
15 Correct 257 ms 211948 KB Output is correct
16 Correct 250 ms 211244 KB Output is correct
17 Correct 266 ms 211284 KB Output is correct
18 Correct 255 ms 211372 KB Output is correct
19 Correct 263 ms 212012 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 205 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7000 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 1 ms 6860 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 2 ms 4444 KB Output is correct
11 Correct 253 ms 209724 KB Output is correct
12 Correct 272 ms 209504 KB Output is correct
13 Correct 262 ms 212004 KB Output is correct
14 Correct 247 ms 212052 KB Output is correct
15 Correct 257 ms 211948 KB Output is correct
16 Correct 250 ms 211244 KB Output is correct
17 Correct 266 ms 211284 KB Output is correct
18 Correct 255 ms 211372 KB Output is correct
19 Correct 263 ms 212012 KB Output is correct
20 Runtime error 205 ms 524288 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -