Submission #720707

#	Time	Username	Problem	Language	Result	Execution time	Memory
720707		PenguinsAreCute	Split the sequence (APIO14_sequence)	C++17	60 / 100	110 ms	131072 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define LL_MAX LONG_LONG_MAX
#define LL_MIN LONG_LONG_MIN
#define speed ios_base::sync_with_stdio(false); cin.tie(0)
#define stMx(a,b) a = max(a,b)
#define stMn(a,b) a = min(a,b)
typedef pair<int,int> ii;
typedef pair<ii,int> iii;
typedef vector<int> vi;
typedef set<int> si;
typedef vector<ii> vii;
typedef set<ii> sii;
#define REP(i, a, b) for(int i = a; i < b; i++)
#define float long double
deque<iii> dq;
int ufds[100005];
int find_set(int x) {
    //printf("Finding set for %d\n", x);
    return ufds[x] = ((ufds[x] == x) ? x : find_set(ufds[x]));
}
void merge_set(int x, int y) {
    ufds[find_set(x)] = ufds[find_set(y)];
}
int f(ii line, int x) {
    return line.fi * x + line.se;
}
ii query(int x) {
    while(dq.size() > 1) {
        if(f(dq[0].fi, x) < f(dq[1].fi, x)) dq.pop_front();
        else break;
    }
    return mp(f(dq[0].fi, x),dq[0].se);
}
float intersect(int a, int b, int c, int d) {
    return (float)(d - b) / (a - c);
}
float intersect(ii p1, ii p2) {
    return intersect(p1.fi, p1.se, p2.fi, p2.se);
}
void ins(int m, int c, int idx) {
    ii line = ii(m, c);
    while(dq.size() > 1) {
        int s = dq.size();
        if(intersect(dq[s - 1].fi, line) <= intersect(dq[s - 2].fi, line)) dq.pop_back();
        else break;
    }
    dq.push_back(mp(line,idx));
}
int32_t main() {
    int n, k; cin >> n >> k; int x[n + 1]; x[0] = 0;
    REP(i, 1, n + 1) {
        cin >> x[i];
        x[i] += x[i - 1];
    }
    pair<int,int> dp[n + 1][k + 1];
    REP(i, 0, n + 1) dp[i][0] = mp(0,0);
    REP(i, 1, k + 1) dp[0][i] = mp(0,0);
    REP(j, 1, k + 1) {
        while(!dq.empty()) dq.pop_back();
        ins(0, 0, 0);
        REP(i, 1, n + 1) {
            dp[i][j] = query(x[i]);
            ins(x[i], dp[i][j - 1].fi - x[i] * x[i], i);
            //printf("Pushed back %d %d into convex hull\n", x[i], dp[i][j - 1].fi - x[i] * x[i]);
        }
    }
    cout << dp[n][k].fi << "\n";
    vector<int> v; int cur = n;
    for(int i = k; i > 0; i--) {
        v.pb(dp[cur][i].se);
        cur = dp[cur][i].se;
    }
    while(!v.empty()) {
        if(v.back() > 0) {
            cout << v.back() << " ";
            ufds[v.back()] = v.back();
            if(ufds[v.back() + 1]) merge_set(v.back(), v.back() + 1);
            if(ufds[v.back() - 1]) merge_set(v.back() - 1, v.back());
        } else {
            int x = find_set(1);
            cout << x + 1 << " ";
            if(x == 0) {
                ufds[0] = 1;
                ufds[1] = 1;
            } else {
                if(!ufds[x + 1]) ufds[x + 1] = x + 1;
                merge_set(x, x + 1);
            }
            //printf("%d\n", find_set(1));
        }
        v.pop_back();
    }
}

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