Submission #1225134

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225134		Icelast	Candies (JOI18_candies)	C++20	0 / 100	5095 ms	532 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];
    }
    auto f = [&](auto f, int L, int R, int ls, int rs) -> vector<ll>{
        if(L == R){
            if(ls != rs){
                return {-INF, -INF};
            }
            if(ls == 0){
                return {0, -INF};
            }
            if(ls == 1){
                return {-INF, a[L]};
            }
        }
        int M = (L+R)/2;
        vector<ll> c(R-L+2), t;
        for(int rs1 = 0; rs1 <= 1; rs1++){
            for(int ls2 = 0; ls2 <= 1; ls2++){
                if((rs1&ls2) == 0){
                    t = concave_max_plus_convolution<ll>(f(f, L, M, ls, rs1), f(f, M+1, R, ls2, rs));
                    for(int i = 0; i < (int)t.size(); i++){
                        c[i] = max(c[i], t[i]);
                    }
                }
            }
        }
        return c;
    };
    vector<ll> ans(n+1), t;
    for(int ls = 0; ls <= 1; ls++) for(int rs = 0; rs <= 1; rs++){
        t = f(f, 1, n, ls, rs);
        for(int i = 1; i <= (n+1)/2; i++){
            ans[i] = max(ans[i], t[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: 0 / 8
• Subtask 2: 0 / 92