이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |