oj.uz

답안 #146009

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
146009 2019-08-21T14:49:05 Z fedoseevtimofey 3단 점프 (JOI19_jumps) C++14
19 / 100
 870 ms 524288 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.setf(ios::fixed); cout.precision(20);
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    int n;
    cin >> n;
    vector <int> A(n);
    for (int i = 0; i < n; ++i) cin >> A[i];
    vector <vector <int>> mx(n, vector <int> (n));
    for (int l = 0; l < n; ++l) {
        for (int r = 0; r < n; ++r) {
            if (r > l) mx[l][r] = max(mx[l][r - 1], A[r]);
            else mx[l][r] = A[r];
        }
    }
    vector <vector <int>> dp(n, vector <int> (n));
    for (int len = 3; len <= n; ++len) {
        for (int l = 0; l + len <= n; ++l) {
            int r = l + len - 1;
            dp[l][r] = max(dp[l + 1][r], dp[l][r - 1]);
            int m = (l + r) >> 1;
            dp[l][r] = max(dp[l][r], A[l] + A[r] + mx[l + 1][m]);
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        --l, --r;
        cout << dp[l][r] << '\n';
    }
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 408 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 408 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 839 ms 206108 KB Output is correct
12 Correct 844 ms 206200 KB Output is correct
13 Correct 837 ms 206248 KB Output is correct
14 Correct 838 ms 206200 KB Output is correct
15 Correct 842 ms 206300 KB Output is correct
16 Correct 860 ms 205560 KB Output is correct
17 Correct 859 ms 205572 KB Output is correct
18 Correct 870 ms 205516 KB Output is correct
19 Correct 835 ms 206032 KB Output is correct

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 455 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 408 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 839 ms 206108 KB Output is correct
12 Correct 844 ms 206200 KB Output is correct
13 Correct 837 ms 206248 KB Output is correct
14 Correct 838 ms 206200 KB Output is correct
15 Correct 842 ms 206300 KB Output is correct
16 Correct 860 ms 205560 KB Output is correct
17 Correct 859 ms 205572 KB Output is correct
18 Correct 870 ms 205516 KB Output is correct
19 Correct 835 ms 206032 KB Output is correct
20 Runtime error 455 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -