Submission #797373

#	Time	Username	Problem	Language	Result	Execution time	Memory
797373		fatemetmhr	Triple Jump (JOI19_jumps)	C++17	5 / 100	4046 ms	18772 KiB

jumps

// Be name khoda // 
 
#include <bits/stdc++.h>
 
#define all(x) x.begin(), x.end()
#define pb     push_back
#define fi     first
#define se     second
#define mp     make_pair
 
typedef long long ll;
 
using namespace std;
 
const int maxn5 = 1e6 + 10;
const int lg    = 20;
const ll inf    = 1e18;
 
ll a[maxn5];

namespace rmq{
    int mx[lg][maxn5];
    void build(int n){
        for(int i = 1; i < lg; i++) for(int j = 0; j < n; j++)
            mx[i][j] = max(mx[i - 1][j], j + (1 << (i - 1)) < n ? mx[i - 1][j + (1 << (i - 1))] : 0);
    }

    ll get_max(int l, int r){
        int k = 31 - __builtin_clz(r - l + 1);
        return max(mx[k][l], mx[k][r - (1 << k) + 1]);
    }
}
 
 
ll solve(int l, int r){
    ll ans = 0;
    for(int i = l + 1; i < r - 1; i++){
        ll mx = 0;
        int op = 0;
        for(int j = i + 1; j < r; j++){
            int len = j - i;
            ll val = rmq::get_max(j, r - 1) + rmq::get_max(max(l, i - len), i - 1) + a[i];
            //cout << i << ' ' << j << ' ' << val << endl;
            if(val >= mx){
                mx = val;
                op = j;
            }
        }
        ans = max(ans, mx);
    }
    return ans;
}
 
int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
 
	int n; cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        rmq::mx[0][i] = a[i];
    }
    rmq::build(n);
    int q; cin >> q;
    while(q--){
        int l, r; cin >> l >> r;
        l--;
        cout << solve(l, r) << '\n';
    }
 
}

Compilation message (stderr)

jumps.cpp: In function 'll solve(int, int)':
jumps.cpp:39:13: warning: variable 'op' set but not used [-Wunused-but-set-variable]
   39 |         int op = 0;
      |             ^~

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