제출 #1210500

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1210500		niepamietamhasla	수열 (APIO14_sequence)	C++20	0 / 100	0 ms	328 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

const ll MAXN = 1e5 + 5;

ll n, k;
ll A[MAXN];
ll P[MAXN];

ll poprz[MAXN];
ll curr[MAXN];
int powrot[MAXN][201];

struct Node{
    pair<ll,ll> F;
    int ind;
    Node *l, *r;

    Node(ll a, ll b, ll c) : F({a,b}), ind(c), l(nullptr), r(nullptr) {}
    Node(Node *ll, Node *rr) : l(ll), r(rr) {}
};

ll base = 1 << 30;
Node *roots[MAXN];

bool mniejsza(pair<ll,ll> f1, pair<ll,ll> f2, ll x){
    if(f1.first * x + f1.second <= f2.first * x + f2.second) return true;
    return false;
}

void dodajprosta(Node *curr, ll akt_a, ll akt_b, pair<ll,ll> nowa, int ind){
    //cout << akt_a << " " << akt_b << " aktualizacja\n";
    //cout << nowa.first << " " << nowa.second << " NOWA\n";
    //cout << curr->F.first << " " << curr->F.second << " curr\n";
    ll mid = (akt_a + akt_b) / 2;
    bool czy = mniejsza(nowa, curr->F, mid);
    //cout << czy << " czy\n";
    if(czy){
        swap(curr->F, nowa);
        swap(curr->ind, ind);
    }
    if(akt_a == akt_b) return;
    if(mniejsza(curr->F, nowa, akt_a) ^ czy == 1){
        if(curr->l == nullptr) curr->l = new Node(0, 1e9, -1);
        dodajprosta(curr->l, akt_a, mid, nowa, ind);
    }
    else{
        if(curr->r == nullptr) curr->r = new Node(0, 1e9, -1);
        dodajprosta(curr->r, mid + 1, akt_b, nowa, ind);
    }
}

void usun(Node *x){
    if(x->l) usun(x->l);
    if(x->r) usun(x->r);
    delete(x);
    return;
}


pair<pair<ll,ll>, int> minval(Node *curr, ll akt_a, ll akt_b, ll gdzie){
    //cout << akt_a << " " << akt_b << " " << curr->F.first << " " << curr->F.second << " funkcja\n";
    if(akt_a == akt_b and akt_a == gdzie){
        return {{curr->F}, curr->ind};
    }
    ll mid = (akt_a + akt_b) / 2;
    if(gdzie <= mid){
        if(curr->l == nullptr) curr->l = new Node(0, 1e9, -1);
        pair<pair<ll,ll>, int> F2 = minval(curr->l, akt_a, mid, gdzie);
        if(mniejsza(curr->F, F2.first, gdzie)) return {curr->F, curr->ind};
        return F2;
    }
    else{
        if(curr->r == nullptr) curr->r = new Node(0, 1e9, -1);
        pair<pair<ll,ll>, int> F2 = minval(curr->r, mid + 1, akt_b, gdzie);
        if(mniejsza(curr->F, F2.first, gdzie)) return {curr->F, curr->ind};
        return F2;
    }
}

int main(){
    // ios_base::sync_with_stdio(0);
    // cin.tie(0);
    // cout.tie(0);
    cin >> n >> k;
    for(ll i = 1; i <= n; ++i){
        cin >> A[i];
        P[i] = P[i - 1] + A[i];
    }
    for(int i = 1; i <= n; ++i){
        poprz[i] = 1e9;
        powrot[i][0] = -1;
    }
    powrot[0][0] = -1;
    for(ll i = 1; i <= k+1; ++i){
        roots[0] = new Node(0, 1e9, -1);
        //cout << "#\n";
        for(ll j = i; j <= n; ++j){
            //cout << "dodaj ind: " << j-1 << " a: " << -2*P[j-1] << " b: " << P[j-1]*P[j-1] << " + " << poprz[j-1] << "\n";
            dodajprosta(roots[0], 0, base - 1, {-2*P[j-1], P[j-1]*P[j-1] + poprz[j-1]}, j-1);
            auto u = minval(roots[0], 0, base -1, P[j]);
            //cout << u.first << " " << u.second << " u\n";
            //cout << u.second << " powrot\n";
            //cout << P[j] << " Pj\n";
            curr[j] = P[j] * P[j] + P[j] * u.first.first + u.first.second;
            //cout << i << " " << j << " " << u.second << " ustaw pow\n";
            powrot[j][i] = u.second;
        }
        //cout << "#\n";
        for(ll j = n; j > i-1; --j){
            //cout << "i: " << i << " j: " << j << " " << curr[j] << " DP\n";
            poprz[j] = curr[j];
            curr[j] = 0;
        }
        poprz[i-1] = 1e9;
        for(int j = 0; j < i; ++j){
            powrot[j][i] = -1;
        }
        usun(roots[0]);
    }
    cout << (P[n] * P[n] - poprz[n]) / 2 << "\n";
    vector<ll> ans;
    ll curr = n;
    ll ind = k+1;
    while(powrot[curr][ind] != 0){
        //cout << curr << " " << ind << " " << powrot[curr][ind] << " pow\n";
        ans.push_back(powrot[curr][ind]);
        curr = powrot[curr][ind];
        ind--;
    }
    reverse(ans.begin(),ans.end());
    for(auto u : ans){
        cout << u << " ";
    }
    cout << "\n";
    return 0;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29