Submission #916041

#	Time	Username	Problem	Language	Result	Execution time	Memory
916041		manizare	Candies (JOI18_candies)	C++14	100 / 100	367 ms	13760 KiB

candies

#include<bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")


#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define ll long long
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= (b);i++)
#define per(i , a , b) for(int i=a;i >= (b);i--)
#define deb(x) cerr<<#x << " : " << x << "\n"; 

using namespace std ;   
const ll maxn = 4e5 + 10 ,  mod = 1e9 + 7 , inf =1e14  ;
int a[maxn];
 
vector<ll> comb(vector<ll> a, vector<ll> b){
    vector <ll>res(sz(a) + sz(b)-1); 
    int id0 = 0 , id1 =0 ;
    while(!(id0 == sz(a)-1 && id1 == sz(b)-1)){
        res[id0+id1] = a[id0] + b[id1] ;
        if(id0!=sz(a)-1 && (id1==sz(b)-1 || a[id0+1]-a[id0] > b[id1+1]-b[id1])){
            id0++;
        }else{
            id1++;
        }
    }
    res[sz(a)+sz(b)-2] = a.back() + b.back() ;
    return res; 
}
 
vector<vector<vector<ll>>> slv(int l, int r){
     if(l + 1 == r){
          return {{{0, -inf}, {-inf, -inf}}, {{-inf, -inf}, {-inf, a[l]}}};
     }
     int mid = (l + r)>>1;
     auto resl = slv(l, mid), resr = slv(mid, r);
     int len = (r - l + 1)/2 + 1;
     vector<vector<vector<ll>>> res(2, vector<vector<ll>>(2));
     rep(i,0,1){
          rep(j,0,1){
               res[i][j] = comb(resl[i][0], resr[0][j]);
               rep(t,0,1){
                    vector<ll> tmp = comb(resl[i][t], resr[t^1][j]);
                    rep(k,0,sz(tmp)-1) res[i][j][k] = max(res[i][j][k], tmp[k]); 
               }
               res[i][j].resize(len);
          }
     }
     return res;
}
 
int main(){
    ios::sync_with_stdio(0) ;cin.tie(0);
     int n; cin >> n;
     rep(i,0,n-1) cin >> a[i];
     auto res = slv(0, n);
     vector<ll> ans = res[0][0];
     rep(i,0,1) rep(j,0,1){
          rep(k,0,sz(ans)-1) ans[k] = max(ans[k], res[i][j][k]);
     }
     rep(i,1,((n+1)>>1)){
          cout << ans[i] << '\n';
     }
     return 0-0;
}

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