oj.uz

답안 #135044

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
135044 2019-07-23T14:57:12 Z qrno 수열 (APIO14_sequence) C++14
0 / 100
 34 ms 1824 KB 
#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;
        }
    }

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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB contestant found the optimal answer: 108 == 108
2 Incorrect 2 ms 376 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 376 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 376 KB contestant found the optimal answer: 610590000 == 610590000
2 Correct 2 ms 256 KB contestant found the optimal answer: 311760000 == 311760000
3 Correct 6 ms 376 KB contestant found the optimal answer: 1989216017013 == 1989216017013
4 Correct 2 ms 256 KB contestant found the optimal answer: 1499437552673 == 1499437552673
5 Correct 2 ms 256 KB contestant found the optimal answer: 1019625819 == 1019625819
6 Incorrect 2 ms 376 KB position 3 occurs twice in split scheme
7 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 1440 KB contestant found the optimal answer: 19795776960 == 19795776960
2 Incorrect 29 ms 1824 KB contestant didn't find the optimal answer: 19874432171 < 19874432173
3 Halted 0 ms 0 KB -