oj.uz

Submission #807261

# Submission time Handle Problem Language Result Execution time Memory
807261 2023-08-04T15:18:33 Z thimote75 Triple Jump (JOI19_jumps) C++14
0 / 100
 219 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 = N - 1; L >= 0; L --) {
        for (int R = L + 2; R < N; R ++) {
            opt[L][R] = opt[L][R - 1];
            if (L != N - 1) opt[L][R] = max(opt[L][R], opt[L + 1][R]);
            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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 219 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 1 ms 212 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -