Submission #1013020

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013020		feev1x	Triple Jump (JOI19_jumps)	C++17	19 / 100	272 ms	524288 KiB

jumps

/**
 *    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 / 5
• Subtask 2: 14 / 14
• Subtask 3: 0 / 27
• Subtask 4: 0 / 54