#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
#define int long long
const int mxn=1e5,mod=29947,lg=25,inf=1e18;
int root;
int dp[500][2][2][500],ans[500][2][mxn+10];
int dp2[500][500][2],cnt=0,m;
//block containing prefix,suffix,take
void solve(vector<int>v){
memset(dp2,0,sizeof dp2);
if(v.size()==0)return;
/*
cout<<cnt<<"B\n";
for(auto i:v)cout<<i<<" ";
cout<<'\n';
*/
if(v.size()==1){
dp[cnt][1][1][1]=v[0];
return;
}
dp2[0][1][1]=v[0];
dp2[1][1][0]=v[1];
dp2[1][1][1]=v[0];
for(int i=2;i<v.size()-1;i++)
for(int t=1;t<=(v.size()+1)/2;t++){//0 0, 0 1 , 1 0 , 1 1
for(int j=0;j<2;j++){
dp2[i][t][j]=dp2[i-1][t][j];
if(dp2[i-2][t-1][j]||t==1)dp2[i][t][j]=max(dp2[i][t][j],dp2[i-2][t-1][j]+v[i]);
}
}
for(int i=1;i<=(v.size()+1)/2;i++){
int a=0,b=0;
if(v.size()>=3)a=dp2[v.size()-3][i-1][0],b=dp2[v.size()-3][i-1][1];
dp[cnt][0][1][i]=dp2[v.size()-3][i-1][0]+v[v.size()-1];
dp[cnt][0][0][i]=dp2[v.size()-2][i][0];
if(v.size()>=3&&dp2[v.size()-3][1])dp[cnt][1][1][i]=dp2[v.size()-3][i-1][1]+v[v.size()-1];
dp[cnt][1][0][i]=dp2[v.size()-2][i][1];
}
}
void solve2(){
for(int i=0;i<=m;i++){
ans[0][0][i]=max(dp[0][0][0][i],dp[0][1][0][i]);
ans[0][1][i]=max(dp[0][0][1][i],dp[0][1][1][i]);
}
for(int i=1;i<cnt;i++){
for(int j=0;j<=m;j++){
ans[i][1][j]=max(ans[i][1][j],ans[i-1][1][j]);
ans[i][0][j]=max(ans[i][0][j],ans[i-1][0][j]);
for(int k=1;k<=root;k++){
ans[i][1][j+k]=max({ans[i-1][0][j]+dp[i][0][1][k],ans[i-1][1][j]+dp[i][0][1][k],ans[i-1][0][j]+dp[i][1][1][k],ans[i][1][j+k]});
ans[i][0][j+k]=max({ans[i-1][0][j]+dp[i][0][0][k],ans[i-1][1][j]+dp[i][0][0][k],ans[i-1][0][j]+dp[i][1][0][k],ans[i][0][j+k]});
}
}
}
}
int32_t main(){
fastio
int n;cin>>n;
m=ceil(n*1.0/2);
vector<int>v(n);
for(int i=0;i<n;i++)cin>>v[i];
root=sqrt(n);
int cur=0;
for(int i=root;i<=n;i+=root){
vector<int>in;
while(cur<=i&&cur<n)in.pb(v[cur++]);
solve(in);
cnt++;
}
/*
for(int i=0;i<cnt;i++){
cout<<"A\n";
for(int j=1;j<=root;j++){
cout<<dp[i][0][1][j]<<" "<<dp[i][1][0][j]<<" "<<dp[i][1][1][j]<<" "<<dp[i][0][0][j]<<'\n';
}
}*/
solve2();
for(int i=1;i<=m;i++)cout<<max(ans[cnt-1][0][i],ans[cnt-1][1][i])<<'\n';
}
Compilation message
candies.cpp: In function 'void solve(std::vector<long long int>)':
candies.cpp:50:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(int i=2;i<v.size()-1;i++)
| ~^~~~~~~~~~~
candies.cpp:51:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for(int t=1;t<=(v.size()+1)/2;t++){//0 0, 0 1 , 1 0 , 1 1
| ~^~~~~~~~~~~~~~~~
candies.cpp:57:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for(int i=1;i<=(v.size()+1)/2;i++){
| ~^~~~~~~~~~~~~~~~
candies.cpp:58:13: warning: variable 'a' set but not used [-Wunused-but-set-variable]
58 | int a=0,b=0;
| ^
candies.cpp:58:17: warning: variable 'b' set but not used [-Wunused-but-set-variable]
58 | int a=0,b=0;
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
12 ms |
9944 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
12 ms |
9944 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
