Submission #129844

#	Time	Username	Problem	Language	Result	Execution time	Memory
129844		RockyB	Candies (JOI18_candies)	C++17	8 / 100	94 ms	32120 KiB

candies

#include <bits/stdc++.h>

#define f first
#define s second

#define sz(x) (int)x.size()

#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, l, r) for (int i = (l); i >= (r); i--)

#define nl '\n'
#define ioi exit(0);

using namespace std;

typedef long long ll;

const int N = (int)2000 + 7;
const ll linf = (ll)1e18 + 7;

int n;
int a[N];

ll dp[N][N];
ll calc(int v, int cnt) {
	if (cnt < 0) return -linf;
	if (v < 1) {
		if (!cnt) return 0;
		return -linf;
	}
	if (~dp[v][cnt]) return dp[v][cnt];
	return dp[v][cnt] = max(calc(v - 1, cnt), calc(v - 2, cnt - 1) + a[v]);
}
int main() {
	ios_base :: sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	#ifdef IOI
		freopen ("in.txt", "r", stdin);
		//freopen ("res.txt", "w", stdout);
	#endif
	cin >> n;
	rep(i, 1, n) {
		cin >> a[i];
	}
	memset(dp, -1, sizeof(dp));
	rep(i, 1, (n + 1) / 2) {
		cout << calc(n, i) << nl;
	}
	ioi
}

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