Submission #1261880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261880		liangjeremy	Candies (JOI18_candies)	C++20	8 / 100	421 ms	589824 KiB

candies

#include<bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;
using db=double;
using ll=int64_t;
using sll=__int128;
using lb=long double;

int32_t main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); srand(time(0));
    int n; cin>>n; vector<int>a(n+1); int m=(n+1)/2; 
    for(int i=1; i<=n; i++){
    	cin>>a[i]; 
    }
    vector<vector<vector<int>>>dp(n+1,vector<vector<int>>(m+1,vector<int>(2,-1e18))); 
    dp[0][0][0]=0; dp[0][0][1]=0;
    for(int i=1; i<=n; i++){
    	dp[i][0][0]=0; dp[i][0][1]=0; 
    	for(int j=1; j<=m; j++){
    		int cst=dp[i-1][j-1][1]; if(i>1)cst=max(cst,dp[i-2][j-1][0]); 
    		dp[i][j][0]=a[i]+cst; dp[i][j][1]=max(dp[i-1][j][0],dp[i-1][j][1]); 
    	}
    }
    for(int i=1; i<=m; i++){
    	cout<<max(dp[n][i][0],dp[n][i][1])<<'\n';
    }
}
/*
O what can ail thee, knight-at-arms,
       Alone and palely loitering?
The sedge has withered from the lake,
       And no birds sing.
 
O what can ail thee, knight-at-arms,
       So haggard and so woe-begone?
The squirrel’s granary is full,
       And the harvest’s done.
 
I see a lily on thy brow,
       With anguish moist and fever-dew,
And on thy cheeks a fading rose
       Fast withereth too. 
*/

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