Submission #46541

#	Time	Username	Problem	Language	Result	Execution time	Memory
46541		tieunhi	Split the sequence (APIO14_sequence)	C++14	100 / 100	827 ms	84980 KiB

sequence

#include <bits/stdc++.h>
#define N 100005
#define PB push_back
#define ll long long

using namespace std;

int n, k, trace[205][N];
ll s[N], dp[N], poller;
vector <long long > v, u, vl, ul, p, pl;
bool check(ll x, ll y, ll z)
{
    return (v[z] - v[x])*(u[x] - u[y]) <= (v[y] - v[x])*(u[x] - u[z]);
}
void add(ll x, ll y, ll vt)
{
    u.PB(x);
    v.PB(y);
    p.PB(vt);
    while (u.size() >= 3 && check(u.size()-3, u.size()-2, u.size()-1))
    {
        u.erase(u.end()-2);
        v.erase(v.end()-2);
        p.erase(p.end()-2);
    }
}
ll get(ll x, ll val)
{
    return ul[x]*val+vl[x];
}
ll get_ans(ll val, int pos)
{
    if (poller >= ul.size()) poller = ul.size()-1;
    while (poller < ul.size()-1 && get(poller+1, val) >= get(poller, val) && pl[poller+1] < pos) poller++;
    return get(poller, val);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("INP.TXT", "r", stdin);
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> s[i];
        s[i] += s[i-1];
    }
    for (int i = 1; i <= n; i++)
    {
        dp[i] = s[i]*(s[n] - s[i]);
        add(s[i], dp[i] - s[i]*s[n], i);
    }
    swap(ul, u); swap(vl, v); swap(pl, p);
    for (int i = 2; i <= k; i++)
    {
        poller = 0;
        for (int j = i; j <= n; j++)
        {
            dp[j] = get_ans(s[j], j) + s[j]*s[n] - s[j]*s[j];
            trace[i][j] = pl[poller];
            add(s[j], dp[j] - s[j]*s[n], j);
        }
        swap(ul, u); swap(vl, v); swap(pl, p);
        u.clear();
        v.clear();
        p.clear();
    }
    ll res = -1; ll pos = 0; ll dem = k;
    for (int i = 1; i < n; i++)
        if (res <= dp[i])
        {
            res = dp[i];
            pos = i;
        }
    cout <<res<<endl;
    vector<int> ans;
    while (dem > 0)
    {
        ans.PB(pos);
        pos = trace[dem--][pos];
    }
    sort(ans.begin(), ans.end());
    for (int &v : ans) cout <<v<<" ";
}

Compilation message (stderr)

sequence.cpp: In function 'long long int get_ans(long long int, int)':
sequence.cpp:33:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (poller >= ul.size()) poller = ul.size()-1;
         ~~~~~~~^~~~~~~~~~~~
sequence.cpp:34:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (poller < ul.size()-1 && get(poller+1, val) >= get(poller, val) && pl[poller+1] < pos) poller++;
            ~~~~~~~^~~~~~~~~~~~~

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