Submission #799090

#	Time	Username	Problem	Language	Result	Execution time	Memory
799090		hungby04	Split the sequence (APIO14_sequence)	C++17	100 / 100	698 ms	83884 KiB

sequence

/// HuDzG
#include <bits/stdc++.h>
#define reset(a) memset(a,0,sizeof(a))
#define ll long long
#define ld long double
#define endl '\n'
#define AutoAC int main()
#define OO 1000000000000000000
#define F first
#define S second
#define pii pair <int, int>
#define pll pair <ll, ll>
#define pb push_back
#define mp make_pair
#define nmax 1000005
#define HUNGIT ""
#define MOD 1000000007

using namespace std;

int n, k;
int a[nmax], tr[205][nmax];
ll sum[nmax], f[2][nmax];

struct Line
{
    ll a, b;
    int id;
    Line(ll a = 0, ll b = 0, int id = 0) : a(a), b(b), id(id) {}

    ll getValue(ll x)
    {
        return a * x + b;
    }
};

double slope(Line A, Line B)
{
    if(A.a == B.a) return (A.b < B.b ? -OO : OO);
    return (double) (A.b - B.b) / (B.a - A.a);
}

void solve()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        sum[i] = sum[i - 1] + 1ll * a[i] * a[i - 1];
        a[i] += a[i - 1];
        f[0][i] = OO;
    }
    // f[k][i] = f[k - 1][j] + sum[i] - sum[j] - (a[i] - a[j]) * a[j];
    for (int j = 1; j <= k + 1; j++)
    {
        int Now = (j & 1), Pre = ((j - 1) & 1);
        deque <Line> D;
        D.push_back(Line(-a[j - 1], f[Pre][j - 1] - sum[j - 1] + 1ll * a[j - 1] * a[j - 1], j - 1));
        for (int i = j; i <= n; i++)
        {
            while (D.size() > 1 && slope(D[0], D[1]) < a[i]) D.pop_front();
            f[Now][i] = D[0].getValue(a[i]) + sum[i];
            tr[j][i] = D[0].id;
            Line tmp(-a[i], f[Pre][i] - sum[i] + 1ll * a[i] * a[i], i);
            while (D.size() > 1 && slope(tmp, D.back()) < slope(D.back(), D[(int)D.size() - 2])) D.pop_back();
            if(tmp.a != D.back().a) D.push_back(tmp);
        }
    }
    cout << sum[n] - f[(k + 1) & 1][n] << endl;
    vector <int> res;
    n = tr[k + 1][n];
    k--;
    while (n > 0)
    {
        res.pb(n);
        n = tr[k + 1][n];
        k--;
    }
    reverse(res.begin(), res.end());
    for (int x : res) cout << x << " ";
    // int res = 0;
    // for(int i = 1; i <= n; i++)
    //     for(int j = 1; j <= n; j++)
    //         if(i != j) res += a[i] * a[j];
    // cout << res / 2;
}

AutoAC
{
    // clock_t START, FINISH;
    // START = clock();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // freopen (HUNGIT".inp", "r", stdin);
    // freopen (HUNGIT".out", "w", stdout);
    int T = 1;

    // cin >> T;

    for (int i = 1; i <= T; i++)
    {
        solve();
    }

    // FINISH = clock();
    // cout << fixed << setprecision(4);
    // cout << endl << "TIME: " << (ld)((ld)(FINISH - START) / CLOCKS_PER_SEC);
    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