Submission #885239

#	Time	Username	Problem	Language	Result	Execution time	Memory
885239		quanlt206	Split the sequence (APIO14_sequence)	C++17	100 / 100	607 ms	89232 KiB

sequence

#include<bits/stdc++.h>
#define X first
#define Y second
#define all(x) begin(x), end(x)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define FORD(i, b, a) for(int i = (b); i >= (a); i--)
#define REP(i, a, b) for (int i = (a); i < (b); i++)
#define mxx max_element
#define mnn min_element
#define SQR(x) (1LL * (x) * (x))
#define MASK(i) (1LL << (i))
#define Point Vector
#define left Left
#define right Right
#define div Div
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
typedef pair<db, db> pdb;
typedef pair<ld, ld> pld;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
typedef pair<ll, int> pli;
typedef pair<ll, pii> plii;
 
template<class A, class B>
    bool maximize(A& x, B y) {
        if (x <= y) return x = y, true; else return false;
    }
template<class A, class B>
    bool minimize(A& x, B y) {
        if (x > y) return x = y, true; else return false;
    }
 
/* END OF TEMPLATE */
 
const int N = 100007;
 
int n, k, a[N];
ll pre[N];
ll f[N], g[N];
 
int trace[207][N];
 
struct Line {
    ll a, b, id;
    Line() {
        a = b = 0;
        id = 0;
    }
    Line(ll a, ll b, int id) : a(a), b(b), id(id) {}
    ll GetVal(ll x) {
        return a * x + b;
    }
};
 
// chu y trung` ho he so goc
 
vector<pair<Line, long double>> E;
 
long double GetIntersection(Line x, Line y) {
    return (long double)(y.b - x.b) / (x.a - y.a);
}
void addLine(Line x) {
    int n = E.size();
    while (n > 1 && GetIntersection(x, E[n - 2].X) <= GetIntersection(E[n - 2].X, E[n - 1].X)) {
        n--;
        E.pop_back();
    }
    if (n == 0) E.push_back({x, -1e18}); else E.push_back({x, GetIntersection(x, E[n - 1].X)});
}
 
int idxE = 0;
pair<ll, int> GetMin(int x) {
    if (E.empty()) return {-1e18, -1};
    minimize(idxE, (int)E.size() - 1);
    while (idxE + 1 < (int)E.size() && E[idxE + 1].Y <= x) idxE++;
    int res = idxE;
    return {E[res].X.GetVal(x), E[res].X.id};
}
 
int main() {
//    freopen("TEST.INP", "r", stdin);
//    freopen("TEST.OUT", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>k;
    FOR(i, 1, n) cin>>a[i], pre[i] = pre[i - 1] + a[i];
    FOR(i, 0, n) g[i] = f[i] = -1e18;
    g[0] = 0;
    FOR(num, 1, k + 1) {
        idxE = 0;
        E.clear();
        int i = 1;
        ll Max0 = g[0], idxMax0 = 0;
        while (i <= n) {
            if (pre[i] == 0) {
                f[i] = Max0;
                if (g[i] != -1e18 && maximize(Max0, g[i])) idxMax0 = i + 1;
                i++;
                continue;
            }
            else {
                if (num == 1) {
                    f[i] = Max0;
                    trace[num][i] = 1;
                }
                int j = i;
                while (j < n && pre[j] == pre[j + 1]) j++;
                ll Max = -1e18, idx = 0;
//                cout<<num<<" "<<i<<" "<<j<<"\n";
                FOR(k, i, j) {
                    pair<ll, int> val = GetMin(pre[k]);
                    f[k] = val.X;
                    trace[num][k] = val.Y;
                    if (Max != -1e18 && maximize(f[k], Max + SQR(pre[k]))) trace[num][k] = idx + 1;
                    if (Max0 > -1e18 && maximize(f[k], Max0)) trace[num][k] = idxMax0;
                    if (g[k] != -1e18 && maximize(Max, g[k] - SQR(pre[k]))) idx = k;
                }
                if (Max != -1e18) addLine(Line(pre[idx], Max, idx + 1));
                i = j + 1;
            }
        }
        FOR(i, 0, n) g[i] = f[i], f[i] = -1e18;
//        FOR(i, 1, n) {
//            FORD(j, i, 1)
//                if (dp[num - 1][j - 1] != -1e18)
//                    if (maximize(dp[num][i], 1LL * (pre[i] - pre[j - 1]) * pre[j - 1] + dp[num - 1][j - 1])) trace[num][i] = j;
//        }
    }
    cout<<g[n]<<"\n";
    vector<int> res;
    k++;
    while (trace[k][n] > 1 && k > 0) {
        res.push_back(trace[k][n] - 1);
        n = trace[k][n] - 1;
        k--;
    }
    reverse(all(res));
    for (auto x : res) cout<<x<<" ";
    return 0;
}

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