이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<stdio.h>
using namespace std;
typedef long long ll;
struct line
{
ll slope, constant;
int num;
line() : slope(0), constant(0), num(0) {}
line(ll a, ll b, int c) : slope(a), constant(b), num(c) {}
};
struct CHT
{
int sz, idx;
line L[100005];
CHT() : sz(0), idx(1) {}
double get_point(line L1, line L2)
{
return (double)(L2.constant-L1.constant)/(L1.slope-L2.slope);
}
bool increase(line L1, line L2, line L3)
{
double p1=get_point(L1,L2);
double p2=get_point(L2,L3);
return p1<=p2;
}
void update(line L3)
{
while(sz>1)
{
line L2=L[sz--];
line L1=L[sz];
if(increase(L1,L2,L3))
{
sz++;
break;
}
}
L[++sz]=L3;
}
ll query(ll x)
{
while(sz-idx+1>1 && get_point(L[idx],L[idx+1])<(double)x)
{
idx++;
}
line L1=L[idx];
return L1.slope*x+L1.constant;
}
int get_line_num()
{
line L1=L[idx];
return L1.num;
}
void clr()
{
idx=1, sz=0;
}
};
int n, k;
ll sum[100005];
ll dp[2][100005], path[205][100005];
CHT cht[2];
int main()
{
scanf("%d %d",&n,&k);
for(int i=1 ; i<=n ; i++)
{
scanf("%lld",&sum[i]);
sum[i]+=sum[i-1];
}
k++;
cht[0].update(line(0,0,0));
for(int i=1 ; i<=k ; i++)
{
int prev=(i-1)%2;
int cur=i%2;
cht[cur].clr();
for(int j=1 ; j<=n ; j++)
{
ll val=cht[prev].query(sum[j]);
dp[cur][j]=val;
path[i][j]=cht[prev].get_line_num();
cht[cur].update(line(sum[j],dp[cur][j]-sum[j]*sum[j],j));
}
}
printf("%lld\n",dp[k%2][n]);
int res[205], cnt=k;
res[k]=n;
while(cnt!=1)
{
res[cnt-1]=path[cnt][res[cnt]];
cnt--;
}
for(int i=1 ; i<k ; i++) printf("%d ",res[i]);
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
sequence.cpp: In function 'int main()':
sequence.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&n,&k);
~~~~~^~~~~~~~~~~~~~~
sequence.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&sum[i]);
~~~~~^~~~~~~~~~~~~~~~
# | 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... |