oj.uz

Submission #1103040

# Submission time Handle Problem Language Result Execution time Memory
1103040 2024-10-19T14:59:25 Z duonggsimp Triple Jump (JOI19_jumps) C++14
32 / 100
 4000 ms 10976 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define xn '\n'
#define pb push_back
#define oo LONG_MAX
using namespace std;

typedef pair<ll,ll> i2;
typedef pair<ll,i2> i3;
typedef pair<i2,ll> i4;

const int N = 1e6+5;
const int M = 1e3+5;
const ll mo = 1e9+7;
 
ll n,m;
ll a[N];
ll c[N];
ll d[N];
ll res;
stack <ll> s;

void sub3(){
    ll l,r; cin >> l >> r;
    for (long i=n; i>=1; i--) c[i] = max(c[i+1],a[i]);
    for (long i=1; i<=n; i++){
        ll j1 = 0;
        while (!s.empty() && a[i] > a[s.top()]) s.pop();
        if (!s.empty()) j1 = s.top();
        s.push(i);
        if (j1 != 0 && i + i - j1 <= n) res = max(res,a[j1]+a[i]+c[i+i-j1]);
    }

    while (!s.empty()) s.pop();
    for (long i=n; i>=1; i--){
        ll j1 = 0;
        while (!s.empty() && a[i] > a[s.top()]) s.pop();
        if (!s.empty()) j1 = s.top();
        s.push(i);
        if (j1 != 0 && j1 + j1 - i <= n) res = max(res,a[j1]+a[i]+c[j1+j1-i]);
    }

    cout << res;
}

void sub1(){
    while (m--){
        ll l,r; cin >> l >> r;
        ll ans = 0;
        for (int i=l; i<=r-2; i ++){
            for (int j=i+1; j<=r-1 ;j++){
                for (int k=j+(j-i); k<=r ; k++){
                ans = max(ans , a[i] + a[j] + a[k]);
            }
        }
    }
    cout << ans << xn;
    }
}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;
    for (long i=1; i<=n; i++) cin >> a[i];
    cin >> m;
    if (m != 1) sub1(); else sub3();
    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 14.0

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

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 8272 KB Output is correct
2 Correct 18 ms 10836 KB Output is correct
3 Correct 18 ms 10976 KB Output is correct
4 Correct 27 ms 9384 KB Output is correct
5 Correct 20 ms 9292 KB Output is correct
6 Correct 18 ms 8532 KB Output is correct
7 Correct 17 ms 8376 KB Output is correct
8 Correct 17 ms 8532 KB Output is correct
9 Correct 18 ms 8788 KB Output is correct

Subtask #4
0 / 54.0

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