Submission #807235

#	Time	Username	Problem	Language	Result	Execution time	Memory
807235		thimote75	Triple Jump (JOI19_jumps)	C++14	19 / 100	1242 ms	524288 KiB

jumps

#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 / 5
• Subtask 2: 14 / 14
• Subtask 3: 0 / 27
• Subtask 4: 0 / 54