oj.uz

Submission #807235

# Submission time Handle Problem Language Result Execution time Memory
807235 2023-08-04T15:08:25 Z thimote75 Triple Jump (JOI19_jumps) C++14
19 / 100
 1242 ms 524288 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

template <typename T>
string to_string (T x) {
    string S = "[";
    bool first = true;
    for (const auto v : x) {
        if (!first) S += ", ";
        first = false;
        S += to_string(v);
    }
    S += "]";
    return S;
}
string to_string (string S) { return S; }
template <typename A, typename B>
string to_string (pair<A, B> p) {
    return "(" + to_string(p.first )+ ", " + to_string(p.second) + ")";
}

void dbg_out () { cout << endl; }
template <typename Head, typename... Tail>
void dbg_out (Head H, Tail... T) {
    cout << to_string(H) << " ";
    dbg_out(T...);
}

#ifdef DEBUG
#  define dbg(...) cout << "(" << #__VA_ARGS__ << "): "; dbg_out(__VA_ARGS__);
#else
#  define dbg(...)
#endif

using idata = vector<int>;
using igrid = vector<idata>;
template<typename T>
using grid = vector<vector<T>>;

igrid opt, dp;

signed main () {
    int N;
    cin >> N;

    idata A(N);
    for (int i = 0; i < N; i ++)
        cin >> A[i];
    
    opt.resize(N, idata(N));
    dp .resize(N, idata(N));

    for (int L = 0; L < N; L ++) {
        for (int R = L + 2; R < N; R ++) {
            opt[L][R] = opt[L][R - 1];
            if (((R - L) & 1) == 0)
                opt[L][R] = max(opt[L][R], A[(L + R) >> 1]);
            
            dp[L][R] = opt[L][R] + A[L] + A[R];
        }
    }

    for (int size = 3; size <= N; size ++) {
        for (int L = 0; L + size - 1 < N; L ++) {
            int R = L + size - 1;

            dp[L][R] = max(
                dp[L][R],
                max(
                    dp[L + 1][R],
                    dp[L][R - 1]
                )
            );
        }
    }

    int Q;
    cin >> Q;

    for (int q = 0; q < Q; q ++) {
        int a, b;
        cin >> a >> b;
        a --;
        b --;

        cout << dp[a][b] << "\n";
    }
}

Subtask #1
5.0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1158 ms 397056 KB Output is correct
12 Correct 1125 ms 401712 KB Output is correct
13 Correct 1167 ms 401812 KB Output is correct
14 Correct 1144 ms 401756 KB Output is correct
15 Correct 1082 ms 401776 KB Output is correct
16 Correct 1235 ms 401092 KB Output is correct
17 Correct 1242 ms 401116 KB Output is correct
18 Correct 1115 ms 401048 KB Output is correct
19 Correct 1150 ms 401712 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 230 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 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1158 ms 397056 KB Output is correct
12 Correct 1125 ms 401712 KB Output is correct
13 Correct 1167 ms 401812 KB Output is correct
14 Correct 1144 ms 401756 KB Output is correct
15 Correct 1082 ms 401776 KB Output is correct
16 Correct 1235 ms 401092 KB Output is correct
17 Correct 1242 ms 401116 KB Output is correct
18 Correct 1115 ms 401048 KB Output is correct
19 Correct 1150 ms 401712 KB Output is correct
20 Runtime error 230 ms 524288 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -