Submission #720716

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

sequence

// usaco guide exists
#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 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);
        }
    }
    cout << dp[n][k].fi << "\n";
    vector<int> v; int cur = n, curzero = 1;
    bool used[n]; REP(i, 0, n) used[i] = false;
    for(int i = k; i > 0; i--) {
        if(dp[cur][i].se > 0) {
            used[dp[cur][i].se] = true;
            v.pb(dp[cur][i].se);
        } else {
            while(used[curzero]) curzero++;
            used[curzero] = true;
            v.pb(curzero);
        }
        cur = dp[cur][i].se;
    }
    sort(v.begin(), v.end());
    for(auto i: v) cout << i << " ";
}

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