Submission #751219

#	Time	Username	Problem	Language	Result	Execution time	Memory
751219		Dan4Life	Candies (JOI18_candies)	C++17	8 / 100	11 ms	16100 KiB

candies

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
const int mxN = (int)2e3+10;
const int LINF = (int)2e18;
int n, a[mxN], dp[mxN][mxN/2];

int32_t main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n; 
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 0; i <= n; i++)
		for(int j = 0; j <= (n+1)/2; j++) 
			dp[i][j] = -LINF;
	dp[0][0]=0;
	for(int i = 1; i <= n; i++){
		for(int j = 0; j <= min(i,(n+1)/2); j++){
			dp[i][j] = dp[i-1][j];
			if(j==1) dp[i][j] = max(dp[i][j], a[i]);
			else if(i>1) dp[i][j] = max(dp[i][j], dp[i-2][j-1]+a[i]);
		}
	}
	for(int i = 1; i <= (n+1)/2; i++) cout << dp[n][i] << "\n";
}

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