Submission #862927

#	Time	Username	Problem	Language	Result	Execution time	Memory
862927		eitanelb	Candies (JOI18_candies)	C++14	100 / 100	372 ms	23828 KiB

candies

#include<bits/stdc++.h> 
#define ll long long 
using namespace std; 
#define all(x) (x).begin(),(x).end() 
#define vll vector<long long> 
#define pvll pair<vll,vll> 
#define x first 
#define y second 
//first index=left 
//1=excluding 
//{{{},{}},{{},{}}}; 
void gtmx(ll&a,ll b){if(b>a)a=b;} 
vll get1(vll f,vll s){ 
    if(!s.size())return f;if(!f.size())return s; 
    int n=f.size()+s.size(); 
    vll toz(n); 
    for(int i=0;f.size()>i;++i)gtmx(toz[i],f[i]); 
    for(int i=0;s.size()>i;++i)gtmx(toz[i],s[i]); 
    int nf=1; 
    for(int i=2;n>=i;++i){ 
        if(i-nf>s.size())++nf; 
        while(nf>1&&i-nf<s.size()&&f[nf-1]+s[i-nf-1]<f[nf-2]+s[i-nf])--nf; 
        while(nf<i-1&&nf<f.size()&&f[nf-1]+s[i-nf-1]<f[nf]+s[i-nf-2])++nf; 
        gtmx(toz[i-1],f[nf-1]+s[i-nf-1]); 
        if(i==4&&toz[i-1]>4000000000){ 
            cout<<"hi\n"; 
        } 
    } 
    return toz; 
} 
vll uni(vll f,vll s){ 
    if(s.size()>f.size())swap(s,f); 
    for(int i=0;s.size()>i;++i)gtmx(f[i],s[i]); 
    return f; 
} 
pair<pvll,pvll> rec (vector<int>&nuts,int st,int en){ 
    if(en-st<=2){ 
        if(en==st)return{{{(ll)nuts[st]},{}},{{},{}}}; 
        if(en==st+1)return {{{max(nuts[st],nuts[en])},{nuts[st]}},{{nuts[en]},{}}}; 
        return {{{max({nuts[st],nuts[st+1],nuts[en]}),nuts[st]+nuts[en]},{max(nuts[st],nuts[st+1])}},{{max(nuts[st+1],nuts[en])},{nuts[st+1]}}}; 
    } 
    int g=(en+st)/2; 
    auto x1=rec(nuts,st,g); 
    auto x2=rec(nuts,g+1,en); 
    return{{uni(get1(x1.x.y,x2.x.x),get1(x1.x.x,x2.y.x)), 
        uni(get1(x1.x.y,x2.x.y),get1(x1.x.x,x2.y.y)) 
    },{uni(get1(x1.y.y,x2.x.x),get1(x1.y.x,x2.y.x)), 
        uni(get1(x1.y.y,x2.x.y),get1(x1.y.x,x2.y.y)) 
    }}; 
} 
vector<long long> Nuts(int N, vector<int> nuts){ 
    return rec(nuts,0,N-1).x.x; 
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin>>n;
    vector<int> nuts(n);
    for(int i=0;i<n;i++) cin>>nuts[i];
    
    vector<long long> ans = Nuts(n, nuts);
    
    for(long long c : ans) cout<<c<<endl;
    return 0;
}

Compilation message (stderr)

candies.cpp: In function 'std::vector<long long int> get1(std::vector<long long int>, std::vector<long long int>)':
candies.cpp:14:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   14 |     if(!s.size())return f;if(!f.size())return s;
      |     ^~
candies.cpp:14:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   14 |     if(!s.size())return f;if(!f.size())return s;
      |                           ^~
candies.cpp:17:25: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   17 |     for(int i=0;f.size()>i;++i)gtmx(toz[i],f[i]);
      |                 ~~~~~~~~^~
candies.cpp:18:25: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   18 |     for(int i=0;s.size()>i;++i)gtmx(toz[i],s[i]);
      |                 ~~~~~~~~^~
candies.cpp:21:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         if(i-nf>s.size())++nf;
      |            ~~~~^~~~~~~~~
candies.cpp:22:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         while(nf>1&&i-nf<s.size()&&f[nf-1]+s[i-nf-1]<f[nf-2]+s[i-nf])--nf;
      |                     ~~~~^~~~~~~~~
candies.cpp:23:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         while(nf<i-1&&nf<f.size()&&f[nf-1]+s[i-nf-1]<f[nf]+s[i-nf-2])++nf;
      |                       ~~^~~~~~~~~
candies.cpp: In function 'std::vector<long long int> uni(std::vector<long long int>, std::vector<long long int>)':
candies.cpp:33:25: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   33 |     for(int i=0;s.size()>i;++i)gtmx(f[i],s[i]);
      |                 ~~~~~~~~^~

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