Submission #1168644

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168644		vladilius	Candies (JOI18_candies)	C++20	0 / 100	2 ms	320 KiB

candies

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define V1 vector<int>
#define V2 vector<V1>
#define V3 vector<V2>
const ll inf = 1e18;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n; cin>>n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++){
        cin>>a[i];
    }
    
    vector<ll> f(n + 1);
    vector<int> s;
    function<V3(int, int)> solve = [&](int l, int r){
        if (l == r){
            V3 dp; dp.resize(2);
            for (int i = 0; i < 2; i++){
                dp[i].resize(2);
            }
            dp[0][0] = {a[l]};
            return dp;
        }
        int m = (l + r) / 2;
        V3 a = solve(l, m), b = solve(m + 1, r), dp;
        dp.resize(2);
        for (int i = 0; i < 2; i++){
            dp[i].resize(2);
        }
        for (int i = 0; i < 2; i++){
            for (int j = 0; j < 2; j++){
                for (int t = 1; t <= (r - l + 1); t++){
                    f[t] = -inf;
                }
                for (int t = 0; t < 2; t++){
                    int i1 = 0, i2 = 0; s.clear();
                    while (i1 < a[i][t].size() || i2 < b[!t][j].size()){
                        if (i1 == a[i][t].size()){
                            s.pb(b[!t][j][i2++]);
                            continue;
                        }
                        if (i2 == b[!t][j].size()){
                            s.pb(a[i][t][i1++]);
                            continue;
                        }
                        if (a[i][t][i1] > b[!t][j][i2]){
                            s.pb(a[i][t][i1++]);
                        }
                        else {
                            s.pb(b[!t][j][i2++]);
                        }
                    }
                    ll sum = 0;
                    for (int x = 0; x < s.size(); x++){
                        sum += s[x];
                        f[x + 1] = max(f[x + 1], sum);
                    }
                }
                
                for (int t = 1; t <= n; t++){
                    if (f[t] == -inf) break;
                    dp[i][j].pb(f[t] - f[t - 1]);
                }
            }
        }
        return dp;
    };
    V3 dp = solve(1, n);
    ll out = 0;
    for (int i: dp[0][0]){
        out += i;
        cout<<out<<" ";
    }
    cout<<"\n";
}

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