Submission #1284924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284924		Johan	3단 점프 (JOI19_jumps)	C++20	0 / 100	28 ms	804 KiB

jumps

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N], st[N * 4];
void build(int v, int l, int r){
  if(l == r){
    st[v] = a[l];
    return ;
  }
  int mid = (l + r) >> 1;
  build(v * 2, l, mid);
  build(v * 2 + 1, mid + 1, r);
  st[v] = max(st[v * 2], st[v * 2 + 1]);
}
int ask(int v, int l, int r, int ql, int qr){
  if(l > qr or r < ql)return 0;
  if(l >= ql && r <= qr)return st[v];
  int mid = (l + r) >> 1;
  return max(ask(v * 2, l, mid, ql, qr), ask(v * 2 + 1, mid + 1, r, ql, qr));
}
int main(){
  int n;
  cin >> n;
  for(int i = 1; i <= n; i++)
    cin >> a[i];
  build(1, 1, n);
  int q;
  cin >> q;
  while(q--){
    int l, r;
    cin >> l >> r;
    int mx = a[r], tot = 0;
    for(int i = r - 1; i >= l; i--){
      // cout << i << ':' << mx << '-' << a[i] << '-' << ask(1, 1, n, max(i - (r - i), l), i - 1) << endl;
      tot = max(tot, mx + a[i] + ask(1, 1, n, max(i - (r - i), l), i - 1));
      mx = max(mx, a[i]);
    }
    cout << tot << endl;
  }
}

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