Submission #134965

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

sequence

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

using namespace std;

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

    Piece() {}
};

struct Cut {
    Piece p;

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

    Cut(Piece P, int LS, int RS, int 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<int> v;
vector<int> 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) {
    int l = p.l;
    int r = p.r;

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

    int ans = -1;

    int 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;
        }
    }

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

int main() {

    int nAmount, sAmount;
    cin >> nAmount >> sAmount;

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

        s += x;
    }

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

    int ans = 0;

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

        for (Piece x : pieces) {
            if (x.r != x.l + 1) {
                Cut c = findSplit(x);
                int v = c.ls * c.rs;
                if (v > maximum)
                    maximum = v, best = c;
            }
        }

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

    cout << ans << endl;
    for (int 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