Submission #572183

#	Time	Username	Problem	Language	Result	Execution time	Memory
572183		teki	Split the sequence (APIO14_sequence)	C++11	0 / 100	28 ms	3824 KiB

sequence

#include <bits/stdc++.h>

typedef long long ll;

#define pb push_back
#define MS(x,y) memset((x),(y),sizeof((x)))
#define MN 1000000001

using namespace std;

int main()
{
    #if LOCAL_DEBUG
        fstream cin("in.txt");
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    ll n,k;
    cin>>n>>k;

    ll niza[n];
    for (ll i = 0; i<n; i++) cin>>niza[i];

    set<ll> podelbi;
    podelbi.insert(n-1);

    int res = 0;

    for (ll ctr = 1; ctr<=k; ctr++) {
        vector<pair<pair<ll,ll>,ll>> site;
        /// start, end, zbir!
        auto itPod = podelbi.begin();
        ll zbir = 0, s = 0;

        for (ll j = 0; j<n; j++) {
            zbir += niza[j];

            if (*itPod == j) {
                site.pb({{s,j},zbir});
                s = j+1;
                zbir = 0;
                itPod++;
            }
        }

        ll ctr2 = 0, l = site[0].first.first, r = site[0].first.second, zb = site[0].second;
        vector<pair<ll,ll>> mozni[ctr];
        ll zbMont = 0;

        for (ll j = 0; j<n; j++) {
            if (r < j) {
                ctr2++;
                l = site[ctr2].first.first;
                r = site[ctr2].first.second;
                zb = site[ctr2].second;
                zbMont = 0;
            }

            zbMont += niza[j];

            mozni[ctr2].pb({(zb-zbMont)*zbMont,j});
        }

        vector<pair<ll,ll>> vistina;
        for (ll j = 0; j<ctr; j++) sort(mozni[j].rbegin(),mozni[j].rend());
        for (ll j = 0; j<ctr; j++) vistina.pb(mozni[j][0]);

        sort(vistina.rbegin(), vistina.rend());
        podelbi.insert(vistina[0].second);

        res += vistina[0].first;
    }

    cout<<res<<endl;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:49:22: warning: variable 'l' set but not used [-Wunused-but-set-variable]
   49 |         ll ctr2 = 0, l = site[0].first.first, r = site[0].first.second, zb = site[0].second;
      |                      ^

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