Submission #101134

#	Time	Username	Problem	Language	Result	Execution time	Memory
101134		TAISA_	Candies (JOI18_candies)	C++14	8 / 100	75 ms	63356 KiB

candies

#include<bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
using namespace std;
using ll=long long;
using P=pair<int,int>;
const ll MOD=1000000007LL;
const ll INF=(1<<30);
const ll LINF=(1LL<<60);
template<typename T> void chmax(T &a,T b){a=max(a,b);}
template<typename T> void chmin(T &a,T b){a=min(a,b);} 
ll dp[2010][2010][2];
int main(){
    int n;cin>>n;if(n>2000)return 0;
    vector<ll> a(n+10);
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)for(int k=0;k<2;k++)dp[i][j][k]=-LINF;
	dp[0][0][0]=0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=i;j++){
			if(j)chmax(dp[i][j][1],dp[i-1][j-1][0]+a[i]);
			chmax(dp[i][j][0],dp[i-1][j][1]);
			chmax(dp[i][j][0],dp[i-1][j][0]);
		}
	}
	for(int i=1;i<=n/2+n%2;i++){
		cout<<max(dp[n][i][0],dp[n][i][1])<<endl;
	}
}

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