제출 #1226249

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1226249		Icelast	Candies (JOI18_candies)	C++17	100 / 100	253 ms	22996 KiB

candies

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
template <class T>
vector<T> concave_max_plus_convolution(const vector<T> &a, const vector<T> &b){
    int n = a.size(), m = b.size();
    vector<T> c(n+m-1);
    c[0] = a[0] + b[0];
    vector<T> slope;
    int j = 1, N = 0;
    for(int i = 1; i < n; i++){
        while(j < m && b[j] - b[j-1] > a[i] - a[i-1]){
            N++;
            c[N] = c[N-1] + b[j] - b[j-1];
            j++;
        }
        N++;
        c[N] = c[N-1] + a[i] - a[i-1];
    }
    while(j < m){
        N++;
        c[N] = c[N-1] + b[j] - b[j-1];
        j++;
    }
    return c;
}
void solve(){
    int n;
    cin >> n;
    vector<ll> a(n+1);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    int cnt = 0;
    auto f = [&](auto f, int L, int R) -> array<vector<ll>, 4>{
        cnt++;
        //cerr<< L << " " << R << " " << cnt << "\n";
        if(L == R){
            array<vector<ll>, 4> res;
            res[0] = {0, -INF};
            res[1] = res[2] = {-INF, -INF};
            res[3] = {-INF, a[L]};
            return res;
        }
        int M = (L+R)/2;
        array<vector<ll>, 4> fL = f(f, L, M), fR = f(f, M+1, R), res;

        for(int l = 0; l <= 1; l++){
            for(int r = 0; r <= 1; r++){
                vector<ll> c(R-L+2, -INF);
                for(int ls = 0; ls <= 1; ls++){
                    for(int rs = 0; rs <= 1; rs++){
                        if(ls && rs) continue;
                        vector<ll> t = concave_max_plus_convolution(fL[l<<1 | rs], fR[ls<<1 | r]);
                        for(int i = 0; i < (int)t.size(); i++){
                            c[i] = max(c[i], t[i]);
                        }
                    }
                }
                res[l<<1 | r] = c;
            }
        }
        return res;
    };
    vector<ll> ans(n+1, 0);
    array<vector<ll>, 4> c;
    c = f(f, 1, n);
    for(int s = 0; s < 4; s++){
        for(int i = 1; i <= (n+1)/2; i++){
            ans[i] = max(ans[i], c[s][i]);
        }
    }
    for(int i = 1; i <= (n+1)/2; i++){
        cout << ans[i] << "\n";
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

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