제출 #1311900

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1311900		al95ireyiz	3단 점프 (JOI19_jumps)	C++20	0 / 100	4090 ms	5948 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>
#define len(x) (ll)x.size()
const ll inf = 1e9, infl = 1e18;
const ll MOD = 1e9 + 7;
const ll maxn = 2e5 + 5;
ll n, m, k = 0;

ll a[maxn], tree[maxn * 4], suff[maxn];
void build(ll l = 1, ll r = n, ll v = 1){
  if(l == r){
    tree[v] = a[l];
    return;
  }
  ll md = (l + r) >> 1;
  build(l, md, v << 1);
  build(md + 1, r, v << 1 | 1);
  tree[v] = max(tree[v << 1], tree[v << 1 | 1]);
}
ll get(ll _l, ll _r, ll l = 1, ll r = n, ll v = 1){
  bool in = _l <= l and r <= _r;
  bool ot = _l <= r and l <= _r;
  if(in) return tree[v];
  if(ot){
    ll md = (l + r) >> 1;
    return max(get(_l, _r, l, md, v << 1), get(_l, _r, md + 1, r, v << 1 | 1));
  }
  return -infl;
}
ll f(ll x, ll y){
  return a[x] + a[y] + get(y + (y - x), n);
}
void _() {
  cin >> n;
  for(ll i = 1; i <= n; i ++){
    cin >> a[i];
  }
  a[n + 1] = -infl;
  build();
  vll v;
  v.push_back(1);
  for(ll i = 2; i <= n; i ++){
    if(get(v.back() + 1, i) < a[v.back()]) continue;
    v.push_back(i);
  }

  v.push_back(n + 1);
  ll cv = -infl, j = 0;
  for(ll i = 1; i <= n; i ++){
    while(j < len(v) and i >= v[j]) j ++;
    ll bf = i;
    for(ll j_ = bf + 1; j_ < v[j]; j_ ++){
      if(get(bf + 1, j_) < a[bf]) continue;
      cv = max(cv, f(i, j_));
    }
    for(ll j_ = j; j_ < len(v); j_ ++){
      cv = max(cv, f(i, v[j_]));
    }
  }

  cin >> m;
  ll l, r;
  cin >> l >> r;
  cout << cv << '\n';

}
signed main() {
  cin.tie(0)->sync_with_stdio(0);
  ll t = 1;
  // cin >> t;
  while(t --) _();
}

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