oj.uz

Submission #526799

# Submission time Handle Problem Language Result Execution time Memory
526799 2022-02-16T07:16:20 Z jalsol Triple Jump (JOI19_jumps) C++11
19 / 100
 325 ms 108216 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 98244 KB Output is correct
2 Correct 42 ms 98240 KB Output is correct
3 Correct 37 ms 98296 KB Output is correct
4 Correct 36 ms 98324 KB Output is correct
5 Correct 36 ms 98340 KB Output is correct
6 Correct 37 ms 98240 KB Output is correct
7 Correct 38 ms 98236 KB Output is correct
8 Correct 47 ms 98244 KB Output is correct
9 Correct 42 ms 98328 KB Output is correct
10 Correct 45 ms 98248 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 98244 KB Output is correct
2 Correct 42 ms 98240 KB Output is correct
3 Correct 37 ms 98296 KB Output is correct
4 Correct 36 ms 98324 KB Output is correct
5 Correct 36 ms 98340 KB Output is correct
6 Correct 37 ms 98240 KB Output is correct
7 Correct 38 ms 98236 KB Output is correct
8 Correct 47 ms 98244 KB Output is correct
9 Correct 42 ms 98328 KB Output is correct
10 Correct 45 ms 98248 KB Output is correct
11 Correct 323 ms 108088 KB Output is correct
12 Correct 308 ms 108068 KB Output is correct
13 Correct 305 ms 108016 KB Output is correct
14 Correct 313 ms 108216 KB Output is correct
15 Correct 302 ms 108084 KB Output is correct
16 Correct 316 ms 107584 KB Output is correct
17 Correct 325 ms 107324 KB Output is correct
18 Correct 302 ms 107344 KB Output is correct
19 Correct 304 ms 107972 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 2796 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 98244 KB Output is correct
2 Correct 42 ms 98240 KB Output is correct
3 Correct 37 ms 98296 KB Output is correct
4 Correct 36 ms 98324 KB Output is correct
5 Correct 36 ms 98340 KB Output is correct
6 Correct 37 ms 98240 KB Output is correct
7 Correct 38 ms 98236 KB Output is correct
8 Correct 47 ms 98244 KB Output is correct
9 Correct 42 ms 98328 KB Output is correct
10 Correct 45 ms 98248 KB Output is correct
11 Correct 323 ms 108088 KB Output is correct
12 Correct 308 ms 108068 KB Output is correct
13 Correct 305 ms 108016 KB Output is correct
14 Correct 313 ms 108216 KB Output is correct
15 Correct 302 ms 108084 KB Output is correct
16 Correct 316 ms 107584 KB Output is correct
17 Correct 325 ms 107324 KB Output is correct
18 Correct 302 ms 107344 KB Output is correct
19 Correct 304 ms 107972 KB Output is correct
20 Incorrect 20 ms 2796 KB Output isn't correct
21 Halted 0 ms 0 KB -