oj.uz

Submission #146009

# Submission time Handle Problem Language Result Execution time Memory
146009 2019-08-21T14:49:05 Z fedoseevtimofey Triple Jump (JOI19_jumps) C++14
19 / 100
 870 ms 524288 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.setf(ios::fixed); cout.precision(20);
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    int n;
    cin >> n;
    vector <int> A(n);
    for (int i = 0; i < n; ++i) cin >> A[i];
    vector <vector <int>> mx(n, vector <int> (n));
    for (int l = 0; l < n; ++l) {
        for (int r = 0; r < n; ++r) {
            if (r > l) mx[l][r] = max(mx[l][r - 1], A[r]);
            else mx[l][r] = A[r];
        }
    }
    vector <vector <int>> dp(n, vector <int> (n));
    for (int len = 3; len <= n; ++len) {
        for (int l = 0; l + len <= n; ++l) {
            int r = l + len - 1;
            dp[l][r] = max(dp[l + 1][r], dp[l][r - 1]);
            int m = (l + r) >> 1;
            dp[l][r] = max(dp[l][r], A[l] + A[r] + mx[l + 1][m]);
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        --l, --r;
        cout << dp[l][r] << '\n';
    }
}

Subtask #1
5.0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 408 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 839 ms 206108 KB Output is correct
12 Correct 844 ms 206200 KB Output is correct
13 Correct 837 ms 206248 KB Output is correct
14 Correct 838 ms 206200 KB Output is correct
15 Correct 842 ms 206300 KB Output is correct
16 Correct 860 ms 205560 KB Output is correct
17 Correct 859 ms 205572 KB Output is correct
18 Correct 870 ms 205516 KB Output is correct
19 Correct 835 ms 206032 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 455 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 408 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 839 ms 206108 KB Output is correct
12 Correct 844 ms 206200 KB Output is correct
13 Correct 837 ms 206248 KB Output is correct
14 Correct 838 ms 206200 KB Output is correct
15 Correct 842 ms 206300 KB Output is correct
16 Correct 860 ms 205560 KB Output is correct
17 Correct 859 ms 205572 KB Output is correct
18 Correct 870 ms 205516 KB Output is correct
19 Correct 835 ms 206032 KB Output is correct
20 Runtime error 455 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -