oj.uz

Submission #1013024

# Submission time Handle Problem Language Result Execution time Memory
1013024 2024-07-03T05:44:28 Z Alihan_8 Triple Jump (JOI19_jumps) C++17
19 / 100
 246 ms 524288 KB 
#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;

    vector <int> a(n + 1);

    for ( int i = 1; i <= n; i++ ){
        cin >> a[i];
    }

    vector <vector<int>> dp(n + 2, vector <int> (n + 2));

    for ( int i = n - 2; i > 0; i-- ){
        int k = i + 1, mx = 0;

        for ( int j = i + 2; j <= n; j++ ){
            dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

            while ( k < j && k - i <= j - k ){
                chmax(mx, a[k]);

                k++;
            }

            chmax(dp[i][j], mx + a[i] + a[j]);
        }
    }

    int q; cin >> q;

    while ( q-- ){
        int l, r; cin >> l >> r;

        cout << dp[l][r] << ln;
    }

    cout << '\n';
}

Subtask #1
5.0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 392 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 246 ms 201536 KB Output is correct
12 Correct 236 ms 201296 KB Output is correct
13 Correct 243 ms 201496 KB Output is correct
14 Correct 230 ms 201424 KB Output is correct
15 Correct 208 ms 201552 KB Output is correct
16 Correct 208 ms 200896 KB Output is correct
17 Correct 222 ms 200788 KB Output is correct
18 Correct 236 ms 200788 KB Output is correct
19 Correct 229 ms 201240 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 203 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 392 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 246 ms 201536 KB Output is correct
12 Correct 236 ms 201296 KB Output is correct
13 Correct 243 ms 201496 KB Output is correct
14 Correct 230 ms 201424 KB Output is correct
15 Correct 208 ms 201552 KB Output is correct
16 Correct 208 ms 200896 KB Output is correct
17 Correct 222 ms 200788 KB Output is correct
18 Correct 236 ms 200788 KB Output is correct
19 Correct 229 ms 201240 KB Output is correct
20 Runtime error 203 ms 524288 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -