oj.uz

Submission #797373

# Submission time Handle Problem Language Result Execution time Memory
797373 2023-07-29T10:08:40 Z fatemetmhr Triple Jump (JOI19_jumps) C++17
5 / 100
 4000 ms 18772 KB 
// 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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 456 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 1 ms 496 KB Output is correct
10 Correct 1 ms 468 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 456 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 1 ms 496 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Execution timed out 4046 ms 1140 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4027 ms 18772 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 456 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 1 ms 496 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Execution timed out 4046 ms 1140 KB Time limit exceeded
12 Halted 0 ms 0 KB -