답안 #134965

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
134965	2019-07-23T13:31:33 Z	qrno	수열 (APIO14_sequence)	C++14	0 / 100	28 ms	1012 KB

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.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	256 KB	contestant found the optimal answer: 108 == 108
2	Incorrect	2 ms	256 KB	contestant didn't find the optimal answer: 951 < 999
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	2 ms	256 KB	contestant didn't find the optimal answer: 1093726 < 1093956
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	256 KB	contestant found the optimal answer: 610590000 == 610590000
2	Correct	2 ms	380 KB	contestant found the optimal answer: 311760000 == 311760000
3	Incorrect	2 ms	376 KB	Integer 0 violates the range [1, 199]
4	Halted	0 ms	0 KB	-