제출 #14234

#제출 시각아이디문제언어결과실행 시간메모리
14234shuuna수열 (APIO14_sequence)C++98
0 / 100
0 ms88056 KiB
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> #include<ctime> #define maxn 210 #define maxm 100010 using namespace std; typedef long long LL; struct Node { LL S,G; int id; Node() {} Node(LL S,LL G,int id): S(S),G(G),id(id) {} }; int pre[maxn][maxm],a[maxm],n,m; LL sum[maxm],dp[maxm]; void read() { scanf("%d %d",&n,&m); for(int i=1;i<=n;++i) { scanf("%d",a+i); sum[i]=sum[i-1]+a[i]; } } void print(int n,int m) { if(n==0) return ; print(n-1,pre[n][m]); printf("%d ",pre[n][m]); } void Dp() { static Node queue[maxm]; for(int i=1;i<=m;++i) { int front=1,rear=1; queue[rear]=Node(dp[i]-sum[i]*sum[i],sum[i],i); for(int j=i+1;j<=n;++j) { while(front<rear&&queue[front].S+sum[j]*queue[front].G<=queue[front+1].S+sum[j]*queue[front+1].G) ++front; Node now(dp[j]-sum[j]*sum[j],sum[j],j); dp[j]=queue[front].S+sum[j]*queue[front].G; pre[i][j]=queue[front].id; while(front<rear&&(now.S-queue[rear].S)*(queue[rear].G-queue[rear-1].G)>=(queue[rear].S-queue[rear-1].S)*(now.G-queue[rear].G)) --rear; queue[++rear]=now; } } cout<<dp[n]<<endl; print(m,n); } int main() { //freopen("sequence.in","r",stdin); //freopen("sequence.out","w",stdout); read(); Dp(); fclose(stdin); fclose(stdout); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...