Submission #1012714

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012714		andrei_iorgulescu	Split the sequence (APIO14_sequence)	C++14	100 / 100	1342 ms	83276 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

using integer = int;

#define int long long

int inf = 5e18;

int n,k,a[100001];
int dp[100001],dpant[100001];
int f[100001];
integer ant[201][100001];

struct dreapta
{
    int offset, panta;

    int eval(int x)
    {
        return offset + panta * x;
    }
};

deque<pair<dreapta,integer>> dq;

long double inters(dreapta d1, dreapta d2)
{
    long double numarator = d2.offset - d1.offset,numitor = d1.panta - d2.panta;
    return numarator / numitor;
}

void update(dreapta d,int pos)
{
    dq.push_back({d,pos});
    while (dq.size() >= 2)
    {
        dreapta d1 = dq.back().first;
        int pos1 = dq.back().second;
        dq.pop_back();
        dreapta d2 = dq.back().first;
        if (d1.panta != d2.panta)
        {
            dq.push_back({d1,pos1});
            break;
        }
        else
        {
            int pos2 = dq.back().second;
            dq.pop_back();
            if (d1.offset > d2.offset)
                dq.push_back({d1,pos1});
            else
                dq.push_back({d2,pos2});
        }
    }
    while (dq.size() >= 3)
    {
        dreapta d1 = dq.back().first;
        int pos1 = dq.back().second;
        dq.pop_back();
        dreapta d2 = dq.back().first;
        int pos2 = dq.back().second;
        dq.pop_back();
        dreapta d3 = dq.back().first;
        int pos3 = dq.back().second;
        dq.pop_back();
        if (inters(d1,d2) >= inters(d2,d3))
        {
            dq.push_back({d3,pos3});
            dq.push_back({d1,pos1});
        }
        else
        {
            dq.push_back({d3,pos3});
            dq.push_back({d2,pos2});
            dq.push_back({d1,pos1});
            break;
        }
    }
}

int query(int x)
{
    if (dq.empty())
        return -inf;
    while (dq.size() >= 2)
    {
        dreapta d1 = dq.front().first;
        int pos1 = dq.front().second;
        dq.pop_front();
        dreapta d2 = dq.front().first;
        if (d1.eval(x) > d2.eval(x))
        {
            dq.push_front({d1,pos1});
            break;
        }
    }
    return dq.front().first.eval(x);
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    f[n] = a[n];
    for (int i = n - 1; i >= 1; i--)
        f[i] = f[i + 1] + a[i];
    dpant[1] = 0;
    for (int i = 2; i <= n; i++)
        dpant[i] = -inf;
    for (int j = 1; j <= k; j++)
    {
        dq.clear();
        for (int i = 1; i <= n; i++)
        {
            dp[i] = query(f[i]) - f[i] * f[i];
            if (!dq.empty())
                ant[j][i] = dq.front().second;
            dreapta aux;
            aux.offset = dpant[i];
            aux.panta = f[i];
            update(aux,i);
        }
        for (int i = 1; i <= n; i++)
            dpant[i] = dp[i];
    }
    int ans = 0;
    for (int i = k + 1; i <= n; i++)
        ans = max(ans,dp[i]);
    cout << ans << '\n';
    int cine;
    for (int i = k + 1; i <= n; i++)
        if (dp[i] == ans)
            cine = i;
    vector<int> lol;
    for (int i = k; i >= 1; i--)
    {
        lol.push_back(cine - 1);
        cine = ant[i][cine];
    }
    reverse(lol.begin(),lol.end());
    for (auto it : lol)
        cout << it << ' ';
    return 0;
}

/*
7 3
4 1 3 4 0 2 3
*/

/**
Nu conteaza ordinea operatiilor, so dp[j][i] = facand j splituri pe locuri pana inainte de i (ultimul pe i), care e suma maxima pe care o pot obtine
dp[j][i] = max(dp[j - 1][q < i] + f[i] * (f[q] - f[i]))
f[i] = suma pe sufix de la i incolo

deci am -f[i] * f[i] mereu, vreau maximul din dp[j - 1][q < i] + f[i] * f[q]
Asta e evident CHT, cu update: dreapta dp[j - 1][i] cu panta f[i] si query in f[i]
Query-urile sunt sortate descrescator si update-urile sunt tot descrescator dupa panta
**/

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:144:28: warning: 'cine' may be used uninitialized in this function [-Wmaybe-uninitialized]
  144 |         lol.push_back(cine - 1);
      |                       ~~~~~^~~

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