Submission #1227331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227331		zNatsumi	Triple Jump (JOI19_jumps)	C++20	46 / 100	4098 ms	247264 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

#define int long long
using ii = pair<int, int>;

const int N = 5e5 + 5;
const long long INF = 1e17;

int n, q, a[N];
ii query[N];

namespace sub12{
  const int N = 5e3 + 5;

  int mx[N][N], dp[N][N];

  void solve(){
    for(int i = 1; i <= n; i++)
      for(int j = i; j <= n; j++) mx[i][j] = max(mx[i][j - 1], a[j]);

    for(int i = n; i >= 1; i--)
      for(int j = i + 2; j <= n; j++){
        dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);
        dp[i][j] = max(dp[i][j], a[i] + a[j] + mx[i + 1][(i + j)/2]);
      }
    for(int i = 1; i <= q; i++) cout << dp[query[i].first][query[i].second] << "\n";
  }
}

namespace sub3{
  const int N = 2e5 + 5;

  int mx[N][20], lg[N], dp[N];

  int get(int l, int r){
    if(l > r) return -INF;
    int k = lg[r - l + 1];
    return max(mx[l][k], mx[r - (1 << k) + 1][k]);
  }

  void dnc(int l, int r, int optl, int optr){
    if(l > r) return;
    int mid = l + r >> 1, opt = -1;

    for(int i = optl; i <= min(mid - 1, optr); i++){
      int value = a[mid] + a[i] + get(max(1LL, 2*i - mid), i - 1);

      if(value > dp[mid]){
        dp[mid] = value;
        opt = i;
      }
    }

    dnc(l, mid - 1, optl, opt);
    dnc(mid + 1, r, opt, optr);
  }

  void solve(){
    for(int i = 1; i <= n; i++) mx[i][0] = a[i];

    for(int j = 1; j <= 17; j++)
      for(int i = 1; i + (1 << j) - 1 <= n; i++)
        mx[i][j] = max(mx[i][j - 1], mx[i + (1 << j - 1)][j - 1]);

    for(int i = 2; i <= n; i++) lg[i] = lg[i/2] + 1;

    dnc(1, n, 1, n);

    cout << *max_element(dp + 3, dp + n + 1) << "\n";
  }
}

int32_t main(){
  cin.tie(0)->sync_with_stdio(0);
//  #define task "test"
//  if(fopen(task ".inp", "r")){
//    freopen(task ".inp", "r", stdin);
//    freopen(task ".out", "w", stdout);
//  }
  cin >> n;
  for(int i = 1; i <= n; i++) cin >> a[i];
  cin >> q;
  for(int i = 1; i <= q; i++) cin >> query[i].first >> query[i].second;

  if(n <= 5000) sub12::solve();
  else if(q == 1 && query[1] == make_pair(1LL, n)) sub3::solve();
  else sub12::solve();


  return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 27 / 27
• Subtask 4: 0 / 54