이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct CHT{
struct line{
ll m,c;
int id;
line(ll mm=0,ll cc=0,int i=0){
m=mm;
c=cc;
id=i;
}
ll cal(ll x){
return m*x+c;
}
double intersect(line l){
return 1.0*(c-l.c)/(l.m-m);
}
};
deque<pair<line,double>> dq;
void insert(ll mm,ll cc,int ii){
line nline(mm,cc,ii);
if(!dq.empty()&&dq.front().first.m==nline.m){
if(nline.c>=dq.front().first.c)
dq.pop_front();
else
return;
}
while(dq.size()>1&&dq.back().second>=dq.back().first.intersect(nline))
dq.pop_back();
if(dq.empty())
dq.push_back({nline,0});
else
dq.push_back({nline,nline.intersect(dq.back().first)});
}
pair<ll,int> query(ll x){
while(dq.size()>1){
if(dq[1].second<=x)
dq.pop_front();
else
break;
}
return {dq.front().first.cal(x),dq.front().first.id};
}
void init(){
dq.clear();
insert(0,0,0);
}
};
int n,k;
ll s[100005];
int prv[100005][205];
main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> k;
for(int i=1;i<=n;i++){
cin >> s[i];
s[i]+=s[i-1];
}
vector<ll> dp(n+1,0),ndp(n+1,0);
++k;
for(int j=1;j<=k;j++){
CHT cht;
cht.init();
for(int i=1;i<=n;i++){
pair<int,int> pi=cht.query(s[i]);
ndp[i]=s[n]*s[i]-s[i]*s[i]+pi.first;
prv[i][j]=pi.second;
cht.insert(s[i],-s[i]*s[n]+dp[i],i);
}
dp=ndp;
}
cout << dp[n] << "\n";
int cur=n;
for(int j=k;j>=2;j--){
cur=prv[cur][j];
cout << cur << " ";
}
}
/*
7 3
4 1 3 4 0 2 3
*/
컴파일 시 표준 에러 (stderr) 메시지
sequence.cpp:68:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
68 | main(){
| ^~~~
# | 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... |