제출 #135002

#제출 시각아이디문제언어결과실행 시간메모리
135002qrno수열 (APIO14_sequence)C++14
0 / 100
310 ms1184 KiB
#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; cout << 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...