# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
337491 | tjrwodnjs999 | 수열 (APIO14_sequence) | C++11 | 822 ms | 85228 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ll long long
#define x first
#define y second
using namespace std;
int n,m,arr[100005],pv[100005][205];
ll DP[100005][2],sum[100005];
struct cht{
int s=0,e=0,num[100005];
pair<ll,ll> p[100005];
void clear(){
s=0,e=0;
}
long double cross(pair<ll,ll> a,pair<ll,ll> b){
return 1.0*(a.y-b.y)/(b.x-a.x);
}
ll f(int a,ll b){
return p[a].x*b+p[a].y;
}
pair<ll,int> qry(ll x){
while(s+1<e&&cross(p[s],p[s+1])<=x) s++;
return {f(s,x),num[s]};
}
void udt(ll a,ll b,int k){
p[e]={a,b}; num[e]=k;
if(s<e&&p[e-1].x==p[e].x){
if(p[e-1].y<=p[e].y) p[e-1]=p[e],num[e-1]=num[e];
e--;
}
while(s+1<e&&cross(p[e-2],p[e-1])>=cross(p[e-1],p[e])) num[e-1]=num[e],p[e-1]=p[e--];
e++;
}
} cht;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",arr+i),sum[i]=sum[i-1]+arr[i];
for(int j=1;j<=m;j++){
cht.clear();
for(int i=1;i<=n;i++){
pair<ll,int> qry=cht.qry(sum[i]);
DP[i][j%2]=qry.x; pv[i][j]=qry.y;
cht.udt(sum[i],-sum[i]*sum[i]+DP[i][(j+1)%2],i);
}
}
printf("%lld\n",DP[n][m%2]);
function<void (int,int)> solve = [&](int a,int b){
if(b==0) return;
solve(pv[a][b],b-1);
printf("%d ",pv[a][b]);
return;
};
solve(n,m);
return 0;
}
컴파일 시 표준 에러 (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... |