# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
57056 | Plurm | 수열 (APIO14_sequence) | C++17 | 619 ms | 85940 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <cstdio>
#include <cstring>
int a[100005];
long long dp[100005];
long long qs[100005];
int par[256][100005];
struct cst{
long long M,C;
int idx;
} L1[100005], L2[100005];
int prt[100005];
int ptr1,ptr2;
int csz1,csz2;
inline bool bad(cst x, cst y, cst z){
return (x.M-y.M)*(z.C-x.C) <= (x.M-z.M)*(y.C-x.C);
}
cst o;
int main(){
int n,k;
scanf("%d%d",&n,&k);
k++;
csz1++;
for(int i = 1; i <= n; i++){
scanf("%d",a+i);
qs[i] = qs[i-1] + (long long)a[i];
dp[i] = -1e16;
}
for(int j = 1; j <= k; j++){
csz2 = ptr2 = 0;
for(int i = j; i <= n; i++){
if(ptr1 >= csz1) ptr1 = csz1-1;
while(ptr1 < csz1-1 && (L1[ptr1+1].M-L1[ptr1].M)*qs[i] + L1[ptr1+1].C-L1[ptr1].C > 0) ptr1++;
par[j][i] = L1[ptr1].idx;
dp[i] = L1[ptr1].M*qs[i] + L1[ptr1].C;
o.M = qs[i];
o.C = dp[i]-qs[i]*qs[i];
o.idx = i;
while(csz2 >= 2 && bad(L2[csz2-2],L2[csz2-1],o)) csz2--;
L2[csz2++] = o;
}
for(int i = 0; i < csz2; i++){
L1[i] = L2[i];
}
csz1 = csz2;
ptr1 = ptr2;
}
printf("%lld\n",dp[n]);
int x = n;
csz1 = 0;
for(int j = k; j > 1; j--){
x = par[j][x];
prt[csz1++] = x;
}
for(int i = 0; i < csz1; i++){
printf("%d ",prt[i]);
}
}
컴파일 시 표준 에러 (stderr) 메시지
# | 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... |