제출 #18279

#제출 시각아이디문제언어결과실행 시간메모리
18279mindol수열 (APIO14_sequence)C++98
0 / 100
0 ms84784 KiB
#include<cstdio> #include<stack> using namespace std; long long S[100001]; long long dt[2][100001]; int sel[201][100001]; stack<int> st; struct Elem{long long a,b; int index;}; Elem data[100010]; int s,e; double crossX(long long pa,long long pb,long long qa,long long qb){ return ((double)qb-pb)/((double)pa-qa); } void add(long long a,long long b,int index) { if(s!=e) { if(data[e-1].a==a) { if(data[e-1].b<b) data[e-1]={a,b,index}; return; } } while(e-s>=2) { if(crossX(data[e-2].a,data[e-2].b,data[e-1].a,data[e-1].b)>=crossX(data[e-1].a,data[e-1].b,a,b)) e--; else break; } data[e++]={a,b,index}; } void get_min(long long x) { while(e-s>=2) { if(data[s].a*x+data[s].b<data[s+1].a*x+data[s+1].b) s++; else break; } } int main() { //freopen("input.txt","r",stdin); int N,K; scanf("%d %d",&N,&K); for(int i=1,x;i<=N;i++) scanf("%d",&x),S[i]=S[i-1]+x; for(int i=2;i<=K+1;++i) { s=e=0; add(S[i-1],dt[(i-1)&1][i-1]-S[i-1]*S[i-1],i-1); for(int j=i;j<=N;++j) { get_min(S[j]); dt[i&1][j]=data[s].a*S[j]+data[s].b; sel[i][j]=data[s].index; add(S[j],dt[(i-1)&1][j]-S[j]*S[j],j); } } printf("%lld",dt[(K+1)&1][N]); int now_i=K+1,now_j=sel[K+1][N]; while(now_i!=1) { st.push(now_j); now_i--; now_j=sel[now_i][now_j]; } while(!st.empty()) printf("%d ",st.top()),st.pop(); 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...