Submission #526799

#	Time	Username	Problem	Language	Result	Execution time	Memory
526799		jalsol	Triple Jump (JOI19_jumps)	C++11	19 / 100	325 ms	108216 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

#define Task ""

struct __Init__ {
    __Init__() {
        cin.tie(nullptr)->sync_with_stdio(false);
        if (fopen(Task".inp", "r")) {
            freopen(Task".inp", "r", stdin);
            freopen(Task".out", "w", stdout); }
    }
} __init__;

using ll = long long;

#ifdef LOCAL
#define debug(x) cerr << "[" #x " = " << x << "]\n";
#else
#define debug(...)
#endif // LOCAL

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fi first
#define se second

#define For(i, l, r) for (int i = (l); i <= (r); ++i)
#define Ford(i, r, l) for (int i = (r); i >= (l); --i)
#define Rep(i, n) For (i, 0, (n) - 1)
#define Repd(i, n) Ford (i, (n) - 1, 0)

template<class C> int isz(const C& c) { return c.size(); }
template<class T> bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } return false; }
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; }

constexpr int eps = 1e-9;
constexpr int inf = 1e9;
constexpr ll linf = 1e18;

// =============================================================================

constexpr int maxN = 5e5 + 5;

int n, nq;
int a[maxN];

struct Sub2 {
    static constexpr int maxN = 5005;

    int dp[maxN][maxN];

    void solve() {
        For (i, 1, n - 2) {
            int p = i + 1;
            int mx = a[p];

            For (j, i + 2, n) {
                while (p - i + 1 <= j - p - 1) {
                    chmax(mx, a[++p]);
                }

                dp[i][j] = a[i] + a[j] + mx;
            }
        }

        For (len, 4, n) {
            For (i, 1, n - len + 1) {
                int j = i + len - 1;

                chmax(dp[i][j], max(dp[i][j - 1], dp[i + 1][j]));
            }
        }

        cin >> nq;
        Rep (_, nq) {
            int l, r; cin >> l >> r;
            cout << dp[l][r] << '\n';
        }
    }
};

signed main() {
    cin >> n;
    For (i, 1, n) cin >> a[i];

#define SUB(x) \
    Sub##x* sol = new Sub##x{}; \
    sol->solve(); delete sol

    if (n <= 5000) {
        SUB(2);
    }
}

/*

*/

Compilation message (stderr)

jumps.cpp: In constructor '__Init__::__Init__()':
jumps.cpp:11:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |             freopen(Task".inp", "r", stdin);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:12:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |             freopen(Task".out", "w", stdout); }
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 0 / 27
• Subtask 4: 0 / 54