Submission #615687

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
615687	2022-07-31T11:59:35 Z	bebra	Candies (JOI18_candies)	C++17	8 / 100	720 ms	259428 KB

candies

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = (int)4000;
long long dp[MAX_N][MAX_N / 2][2];
const long long MINUS_INF = -1e15;


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> a(n);
    for (auto& x : a) cin >> x;
    for (int i = 0; i < MAX_N; ++i) {
        for (int j = 0; j < MAX_N / 2; ++j) {
            for (int f = 0; f <= 1; ++f) {
                dp[i][j][f] = MINUS_INF;
            }
        }
    }
    dp[0][0][0] = 0;
    dp[0][1][1] = a[0];
    for (int i = 1; i < n; ++i) {
        dp[i][0][0] = 0;
        for (int j = 1; j <= (n + 1) / 2; ++j) {
            dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1]);
            if (dp[i - 1][j - 1][0] == MINUS_INF) {
                dp[i][j][1] = MINUS_INF;
            } else {
                dp[i][j][1] = dp[i - 1][j - 1][0] + a[i];
            }
        }
    }
    for (int j = 1; j <= (n + 1) / 2; ++j) {
        cout << max(dp[n - 1][j][0], dp[n - 1][j][1]) << '\n';
    }
    return 0;
}

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	61 ms	125516 KB	Output is correct
2	Correct	69 ms	125560 KB	Output is correct
3	Correct	82 ms	125556 KB	Output is correct
4	Correct	60 ms	125588 KB	Output is correct
5	Correct	55 ms	125564 KB	Output is correct
6	Correct	56 ms	125500 KB	Output is correct
7	Correct	55 ms	125476 KB	Output is correct
8	Correct	54 ms	125500 KB	Output is correct
9	Correct	57 ms	125576 KB	Output is correct
10	Correct	54 ms	125540 KB	Output is correct
11	Correct	54 ms	125564 KB	Output is correct
12	Correct	54 ms	125532 KB	Output is correct
13	Correct	69 ms	125492 KB	Output is correct
14	Correct	74 ms	125572 KB	Output is correct
15	Correct	56 ms	125580 KB	Output is correct
16	Correct	63 ms	125516 KB	Output is correct
17	Correct	56 ms	125540 KB	Output is correct
18	Correct	57 ms	125520 KB	Output is correct
19	Correct	67 ms	125592 KB	Output is correct
20	Correct	60 ms	125564 KB	Output is correct

Subtask #2

0 / 92.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	61 ms	125516 KB	Output is correct
2	Correct	69 ms	125560 KB	Output is correct
3	Correct	82 ms	125556 KB	Output is correct
4	Correct	60 ms	125588 KB	Output is correct
5	Correct	55 ms	125564 KB	Output is correct
6	Correct	56 ms	125500 KB	Output is correct
7	Correct	55 ms	125476 KB	Output is correct
8	Correct	54 ms	125500 KB	Output is correct
9	Correct	57 ms	125576 KB	Output is correct
10	Correct	54 ms	125540 KB	Output is correct
11	Correct	54 ms	125564 KB	Output is correct
12	Correct	54 ms	125532 KB	Output is correct
13	Correct	69 ms	125492 KB	Output is correct
14	Correct	74 ms	125572 KB	Output is correct
15	Correct	56 ms	125580 KB	Output is correct
16	Correct	63 ms	125516 KB	Output is correct
17	Correct	56 ms	125540 KB	Output is correct
18	Correct	57 ms	125520 KB	Output is correct
19	Correct	67 ms	125592 KB	Output is correct
20	Correct	60 ms	125564 KB	Output is correct
21	Runtime error	720 ms	259428 KB	Execution killed with signal 11
22	Halted	0 ms	0 KB	-