Submission #855935

#	Time	Username	Problem	Language	Result	Execution time	Memory
855935		8pete8	Candies (JOI18_candies)	C++17	0 / 100	12 ms	9944 KiB

candies

#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 (stderr)

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;
      |                 ^

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