이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define X first
#define Y second
const int N = 1e5 + 1;
typedef pair<ll,ll> ii;
struct ConvexHull {
int tot = 0;
int ptr = 0;
ii line[N];
int name[N];
int bad(ii a,ii b,ii c) {
return 1.0 * (c.Y - a.Y) / (a.X - c.X) <= 1.0 * (b.Y - a.Y) / (a.X - b.X);
}
int add(ll s,ll c,int i){
while (tot > 1) {
if (bad(line[tot - 1],line[tot],ii(s,c))) {
tot--;
continue;
}
break;
}
++tot;
line[tot] = ii(s,c);
name[tot] = i;
}
ll get(int i,int x) {
return line[i].X * x + line[i].Y;
}
ii get(int x) {
for(ptr = min(ptr,tot) ; ptr < tot && get(ptr,x) <= get(ptr + 1,x) ; ++ptr);
return ii(get(ptr,x),name[ptr]);
}
} Combi;
int a[N], c[N];
ll f[N];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n; cin >> n;
int k; cin >> k;
for(int i = 1 ; i <= n ; ++i)
cin >> a[i],
a[i] += a[i - 1];
auto trial = [&](ll D) {
Combi.tot = 0;
Combi.ptr = 1;
Combi.add(0,0,0);
for(int i = 1 ; i <= n ; ++i) {
int j = Combi.get(a[i] * 2).Y;
f[i] = f[j] + 1ll * (a[i] - a[j]) * (a[i] - a[j]) - D;
c[i] = c[j] + 1;
Combi.add(a[i], -f[i] - 1ll * a[i] * a[i],i);
}
return c[n] > k;
};
ll L = -1e13;
ll R = 1e13;
for(; L < R ;) {
ll M = (L + R) / 2;
if (trial(M))
R = M;
else
L = M + 1;
}
trial(L);
ll ans = (1ll * a[n] * a[n] - f[n] - L * (k + 1)) / 2;
cout << ans << "\n";
stack<int> res;
while (n) {
for(int i = n - 1 ; i >= 0 ; --i)
if (f[i] + 1ll * (a[n] - a[i]) * (a[n] - a[i]) - L == f[n]) {
res.push(n);
n = i;
break;
}
}
while (res.size() > 1)
cout << res.top() << " ",
res.pop();
}
/*
7 3
4 1 3 4 0 2 3
*/
컴파일 시 표준 에러 (stderr) 메시지
sequence.cpp: In member function 'int ConvexHull::add(long long int, long long int, int)':
sequence.cpp:34:5: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
# | 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... |