이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define ep emplace
#define all(v) (v).begin(), (v).end()
#define sz(v) (int)v.size()
#define rmin(r, x) r = min(r, x)
#define rmax(r, x) r = max(r, x)
#define ends ' '
#define endl '\n'
#define rep(i, s, e) for(int i = (s); i <= (e); ++i)
#define rep2(i, e, s) for(int i = (e); i >= (s); --i)
#define print(v) copy(all(v), ostream_iterator<int>(cout, " ")), cout << endl
#define fastio ios_base::sync_with_stdio(0), cin.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<int> vi;
// #define LOCAL
const ll inf = 1e18;
const int maxn = 1e5 + 10;
const int maxk = 2e2 + 10;
const ll minx = 0, maxx = 1e9;
int N, K;
ll S[maxn];
ll D[2][maxn];
int P[maxk][maxn];
struct Line {
ll a, b;
int prv;
Line(ll a=0, ll b=-inf, int prv=-1) : a(a), b(b), prv(prv) {}
ll calc(ll x) { return a * x + b; }
};
struct Node {
Line f;
int l, r;
Node() : l(0), r(r) {}
};
struct CHT {
deque<Line> f;
void update(Line g) {
while(sz(f) >= 2) {
Line& t2 = f[sz(f)-2];
Line& t1 = f[sz(f)-1];
// point(2, 0) < point(1, 0): break
if((g.b-t2.b)*(g.a-t1.a) < (g.b-t1.b)*(g.a-t2.a)) break;
f.pop_back();
}
while(not f.empty() and f.back().a == g.a) {
if(f.back().b > g.b) return;
f.pop_back();
}
f.eb(g);
}
pll query(ll x) {
if(f.empty()) return pll(-inf, -1);
while(sz(f) >= 2 and f[0].calc(x) <= f[1].calc(x)) f.pop_front();
return pll(f.front().calc(x), f.front().prv);
}
} cht;
int main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
fastio;
cin >> N >> K;
rep(i, 1, N) {
int x; cin >> x;
S[i] = S[i-1] + x;
}
rep(i, 1, N) P[0][i] = i;
rep(k, 1, K) {
int t = k & 1, _t = !t;
CHT cht;
rep(i, 1, N) {
auto [d, p] = cht.query(S[i]);
D[t][i] = d;
P[k][i] = p;
cht.update(Line(S[i], D[_t][i] - S[i]*S[i], i));
}
}
vector<int> ans;
int idx = N;
rep2(k, K, 1) {
idx = P[k][idx];
ans.eb(idx);
}
reverse(all(ans));
cout << D[K&1][N] << endl;
for(auto& i : ans) cout << i << ends;
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
sequence.cpp: In constructor 'Node::Node()':
sequence.cpp:45:2: warning: 'Node::r' is initialized with itself [-Winit-self]
45 | Node() : l(0), r(r) {}
| ^~~~
# | 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... |