Submission #1046942

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046942		Sharky	Candies (JOI18_candies)	C++17	8 / 100	13 ms	31860 KiB

candies

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

#define int long long
int a[2001], dp[2001][2001], mx[2001];
const int inf = 1e18;

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        mx[i] = max(mx[i - 1], a[i]);
    }
    for (int i = 0; i < 2001; i++) for (int j = 0; j < 2001; j++) dp[i][j] = -inf;
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 0;
        if (i >= 1) dp[i][1] = mx[i];
    }
    for (int j = 2; j <= n; j++) {
        for (int i = 1; i <= n; i++) {
            if (i >= 2) dp[i][j] = max(dp[i - 1][j], dp[i - 2][j - 1] + a[i]);
            else dp[i][j] = dp[i - 1][j];
        }
    }
    for (int i = 1; i <= (n + 1) / 2; i++) cout << dp[n][i] << '\n';
}

• Subtask 1: 8 / 8
• Subtask 2: 0 / 92