이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pii pair<LL,LL>
#define LL long long
#define st first
#define nd second
#define endl '\n'
using namespace std;
const int MAXN=100005,MAXK=201;
LL n,k,sum[MAXN],t,pnt,val[2][MAXN],top;
int used[MAXN][MAXK];
pair<pii,int> line[MAXN];
double inter(pii a,pii b) {
if(a.st==b.st)
return -1e9;
return 1.0*(b.nd-a.nd)/(a.st-b.st);
}
void upd(LL val) {
while(pnt+1<top&&inter(line[pnt].st,line[pnt+1].st)<=1.0*val)
++pnt;
}
void add(pii ll,int y) {
while(top>=2&&inter(line[top-1].st,line[top-2].st)>=inter(ll,line[top-1].st))
--top;
line[top++]=mp(ll,y);
pnt=min(pnt,top-1);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n>>k;
for(int i=1;i<=n;++i) {
cin>>t;
sum[i]=sum[i-1]+t;
}
for(int j=1;j<=k;++j) {
int cur=j&1,old=cur^1;
pnt=top=0;
add(mp(sum[j],-sum[j]*sum[j]+val[old][j]),j);
for(int i=j+1;i<=n;++i) {
upd(sum[i]);
val[cur][i]=line[pnt].st.st*sum[i]+line[pnt].st.nd;
//cout<<j<<" "<<i<<" "<<val[cur][i]<<endl;
used[i][j]=line[pnt].nd;
add(mp(sum[i],-sum[i]*sum[i]+val[old][i]),i);
}
}
cout<<val[k&1][n]<< endl;
int cur=n;
for(int i=k;i>=1;--i) {
cur=used[cur][i];
cout<<cur<<" ";
}
cout<<endl;
}
# | 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... |