Submission #339756

#	Time	Username	Problem	Language	Result	Execution time	Memory
339756		blue	Split the sequence (APIO14_sequence)	C++11	0 / 100	214 ms	6764 KiB

sequence

#include <iostream>
#include <vector>
#include <set>
using namespace std;

long long sq(long long a)
{
    return a*a;
}
/*
int main()
{
    int n, k;
    cin >> n >> k;

    long long a[n+1];
    a[0] = 0;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        a[i] += a[i-1];
    }

    int right[k+2]; //rightmost element belonging to the i'th part from the left.
    right[0] = 0;
    for(int j = 1; j <= k; j++) right[j] = j;
    right[k+1] = n;

    bool flag = 1;

    while(flag)
    {
        flag = 0;
        for(int j = k; j >= 1; j--)
        {
            while(right[j]+1 < right[j+1] && a[ right[j+1] ] - a[ right[j]+1 ] >= a[ right[j] ] - a[ right[j-1] ])
            {
                right[j]++;
                flag = 1;
            }
        }
    }


    long long res = sq(a[n]);
    for(int j = 1; j <= k+1; j++) res -= sq(a[ right[j] ] - a[ right[j-1] ]);
    res /= 2;

    cout << res << '\n';

    for(int i = 1; i <= k; i++) cout << right[i] << ' ';
    cout << '\n';
}*/

long long a[100001];
int nxt[100003]; //barrier i occurs between i and i+1
int prv[100003];

struct barrier
{
    int i;
};

bool operator < (barrier P, barrier Q)
{
    if((a[nxt[P.i]] - a[P.i]) * (a[P.i] - a[prv[P.i]]) == (a[nxt[Q.i]] - a[Q.i]) * (a[Q.i] - a[prv[Q.i]]))
        return P.i < Q.i;
    return (a[nxt[P.i]] - a[P.i]) * (a[P.i] - a[prv[P.i]]) < (a[nxt[Q.i]] - a[Q.i]) * (a[Q.i] - a[prv[Q.i]]);
}

set<barrier> S;

int main()
{
    int n, k;
    cin >> n >> k;

    long long res = 0;

    a[0] = 0;
    nxt[0] = 1;
    prv[0] = -1;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        a[i] += a[i-1];
        nxt[i] = i+1;
        prv[i] = i-1;
    }

    nxt[n] = n+1;
    prv[n] = n-1;

    res = sq(a[n]);
    for(int i = 1; i <= n; i++) res -= sq(a[i] - a[i-1]);
    res /= 2;

    // cout << res << '\n';

    for(int i = 1; i < n; i++) S.insert(barrier{i});
    while(S.size() > k)
    {
        // cout << "________________________________________---\n";
        // for(barrier s:S) cout << s.i << ' ';
        // cout << '\n';
        //
        // for(int i = 1; i < n; i++)
        // {
        //     cout << a[i] - a[i-1];
        //     if(S.find(barrier{i}) != S.end()) cout << '|';
        //     else cout << ' ';
        // }
        // cout << a[n] - a[n-1] << '\n';
        // cout << res << '\n';











        int g = S.begin()->i;
        S.erase(S.begin());
        // cout << S.size() << '\n';

        // cout << "barrier=" << g << ' ' << "nxt=" << nxt[g] << ' ' << "prv=" << prv[g] << '\n';

        if(nxt[g] < n) S.erase(barrier{nxt[g]});
        if(prv[g] > 0) S.erase(barrier{prv[g]});
        prv[nxt[g]] = prv[g];
        nxt[prv[g]] = nxt[g];
        if(nxt[g] < n) S.insert(barrier{nxt[g]});
        if(prv[g] > 0) S.insert(barrier{prv[g]});

        // cout << a[prv[g]] << ' ' << a[g] << ' ' << a[nxt[g]] << '\n';
        res -= (a[nxt[g]] - a[g]) * (a[g] - a[prv[g]]);

        // cout << "temp\n";
    }
    // 
    // for(int i = 1; i < n; i++)
    // {
    //     cout << a[i] - a[i-1];
    //     if(S.find(barrier{i}) != S.end()) cout << '|';
    //     else cout << ' ';
    // }
    // cout << a[n] - a[n-1] << '\n';

    cout << res << '\n';
    for(barrier x:S) cout << x.i << ' ';
    cout << '\n';
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:101:20: warning: comparison of integer expressions of different signedness: 'std::set<barrier>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  101 |     while(S.size() > k)
      |           ~~~~~~~~~^~~

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