oj.uz

답안 #797383

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
797383 2023-07-29T10:14:57 Z fatemetmhr 3단 점프 (JOI19_jumps) C++17
0 / 100
 4000 ms 17828 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){
        if(r < l)
            return -inf;
        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){
    //cout << "While in " << l << ' ' << r << endl;
    ll ans = 0;
    int last = -1;
    for(int i = l + 1; i < r - 1; i++){
        ll mx = 0;
        int op = -1;
        for(int j = i + 2; j < r; j++){
            int len = j - i;
            ll val = rmq::get_max(j, r - 1) + rmq::get_max(max(l, i - len), i - 2) + a[i];
            //cout << i << ' ' << j << ' ' << val << endl;
            if(val >= mx){
                mx = val;
                op = j;
            }
        }
        //cout << i << ' ' << mx << ' ' << op << ' ' << last << endl;
        assert(op == -1 || op >= last);
        last = op;
        ans = max(ans, mx);
    }
    for(int i = l + 1; i < r - 1; i++)
        ans = max(ans, a[i - 1] + a[i] + rmq::get_max(i + 1, r));
    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';
    }
 
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Runtime error 3 ms 724 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Runtime error 3 ms 724 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4046 ms 17828 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Runtime error 3 ms 724 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -