Submission #1183371

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183371		DeMen100ns	Candies (JOI18_candies)	C++17	100 / 100	305 ms	13456 KiB

candies

/*
Author : DeMen100ns (Vo Khac Trieu)
School: University of Science, VNU-HCM
Aim: 
- International Grandmaster Codeforces (2600) 
- ICPC World Final 2025
*/

#include <bits/stdc++.h>

#define int long long

using namespace std;

const long long INF = numeric_limits<long long>::max() / 8;
const int INF_int = 1e9 + 7;

vector <int> max_plus(vector <int> a, vector <int> b){
    // for(int i : a) cout << i << " ";
    // cout << "+ ";
    // for(int i : b) cout << i << " ";
    // cout << "= ";

    int n = a.size(), m = b.size();

    vector <int> ans(n + m - 1, 0);
    ans[0] = a[0] + b[0];
    for(int k = 1, i = 0, j = 0; k < n + m - 1; ++k){
        int option = -1;
        if (i == n - 1){
            option = 1;
        }
        else if (j == m - 1){
            option = 0;
        }
        else{
            if (a[i + 1] - a[i] > b[j + 1] - b[j]){
                option = 0;
            } else option = 1;
        }
        if (!option){
            ans[k] = ans[k - 1] + a[i + 1] - a[i];
            ++i;
        } else {
            ans[k] = ans[k - 1] + b[j + 1] - b[j];
            ++j;
        }
    }

   // for(int i : ans) cout << i << " "; cout << endl;
    return ans;
}

array<vector<int>, 4> dnc(vector <int> &a, int l, int r){
    if (l == r){
        return array<vector<int>, 4>({vector<int>({0}), vector<int>({-INF}), 
        vector<int>({-INF}), vector<int>({-INF, a[l]})});
    }

    int mid = (l + r) >> 1;
    array<vector<int>, 4> L = dnc(a, l, mid), R = dnc(a, mid + 1, r);

    //cout << l << "->" << r << ":" << endl;

    array<vector<int>, 4> res;
    for(int l = 0; l <= 1; ++l){
        for(int r = 0; r <= 1; ++r){
            vector <int> ans = {};
            for(int midl = 0; midl <= 1; ++midl){
                for(int midr = 0; midr <= 1; ++midr){
                    if (midl && midr) continue;
                   // cout << l << "-" << midl << " + " << midr << "-" << r << endl;
                    vector <int> F = max_plus(L[l << 1 | midl], R[midr << 1 | r]);
                    for(int i = 0; i < F.size(); ++i){
                        if (i >= ans.size()) ans.push_back(F[i]);
                        else ans[i] = max(ans[i], F[i]);
                    }
                }
            }
            res[l << 1 | r] = ans;
        }
    }
    return res;
}

void solve(){
    int n; cin >> n;
    vector <int> a(n);
    for(int &x : a) cin >> x;
    
    array<vector<int>, 4> ans = dnc(a, 0, n - 1);
    for(int i = 1; i <= (n + 1) / 2; ++i){
        int res = -1;
        for(int j = 0; j < 4; ++j){
            if (ans[j].size() > i) res = max(res, ans[j][i]);
        }
        if (res == -1) res = 0;
        cout << res << '\n';
    }
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    int t = 1; // cin >> t;
    for(int test = 1; test <= t; ++test){
        solve();
    }
}

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