Submission #135068

#	Time	Username	Problem	Language	Result	Execution time	Memory
135068		qrno	Split the sequence (APIO14_sequence)	C++14	0 / 100	32 ms	1668 KiB

sequence

#include <iostream>
#include <vector>
#include <set>

using namespace std;

typedef long long ll;

struct Piece {
    // PIECE [l r)
    ll s, l, r;
   
    Piece(ll S, ll L, ll R) :
        s(S), l(L), r(R) {}

    Piece() {}
};

struct Cut {
    Piece p;

    // Cut ll [p.l, pos), [pos, p.r)
    ll ls, rs, pos;

    Cut(Piece P, ll LS, ll RS, ll POS) :
        p(P), ls(LS), rs(RS), pos(POS) {}

    Cut() {}
};

inline bool operator <(Piece a, Piece b) {
    return a.l < b.l;
}

set<Piece> pieces;
vector<ll> v;
vector<ll> splits;

void cut(Cut c) {
    pieces.erase(c.p);

    Piece l(c.ls, c.p.l, c.pos);
    Piece r(c.rs, c.pos, c.p.r);

    pieces.insert(l);
    pieces.insert(r);

    splits.push_back(c.pos);
}

Cut findSplit(Piece p) {
    ll l = p.l;
    ll r = p.r;

    ll lSum = 0;
    ll rSum = p.s;

    ll ans = -1;

    ll i;
    for (i = l; i < r; i++) {
        lSum += v[i];
        rSum -= v[i];

        if (lSum * rSum > ans)
            ans = lSum * rSum;
        if (lSum * rSum < ans) {
            lSum -= v[i];
            rSum += v[i];

            Cut c(p, lSum, rSum, i);
            return c;
        }
    }
    i--;

    Cut c(p, lSum, rSum, i);
    return c;
}

int main() {

    ll nAmount, sAmount;
    cin >> nAmount >> sAmount;


    ll s = 0;
    for (ll i = 0; i < nAmount; i++) {
        ll x; cin >> x;
        v.push_back(x);

        s += x;
    }

    Piece p(s, 0, nAmount);
    pieces.insert(p);

    ll ans = 0;

    for (ll i = 0; i < sAmount; i++) {
        ll maximum = -1;
        Cut best;

        for (Piece x : pieces) {
            if (x.r != x.l + 1) {
                Cut c = findSplit(x);
                ll v = c.ls * c.rs;

//                cout << "findSplit[" << x.l << ", " << x.r << ") = " << v << endl;
                if (v > maximum)
                    maximum = v, best = c;
            }
        }

        ans += best.ls * best.rs;
        cut(best);
    }

    cout << ans << endl;
    for (ll v : splits)
        cout << v << " ";
    cout << endl;

    return 0;
}

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