记录编号	590035	评测结果	AAAAAAAAAAA
题目名称	(USACO Dec18)平衡木	最终得分	100
用户昵称	健康铀	是否通过	通过
代码语言	C++	运行时间	0.700 s
提交时间	2024-07-09 14:37:35	内存使用	8.05 MiB

#include<bits/stdc++.h>
using namespace std;
__int128 a[200005];
int q[200005],t1,n,t2;
double f[200005];
void write(__int128 x){
    if(x<=9){
    putchar('0'+x);
    return;
    }
    write(x/10);
    putchar('0'+x%10);
}
int main(){
    freopen("balance_beam.in","r",stdin);
    freopen("balance_beam.out","w",stdout);
    cin>>n;
    q[t1=1]=0;
    for(int i=1;i<=n+1;i++){
        if(i<=n){
           long long x;
           cin>>x;
           a[i]=x*100000; 
        }
        while(t1>1&&(q[t1]-q[t1-1])*(a[q[t1]]-a[i])-(q[t1]-i)*(a[q[t1]]-a[q[t1-1]])<=0)
        t1--;
        q[++t1]=i;
    }
    for(int i=1;i<=n;i++){
        while(q[t2+1]<=i)t2++;
        write(((((q[t2+1]-i)*a[q[t2]])+(i-q[t2])*a[q[t2+1]])/(q[t2+1]-q[t2])));
        printf("\n");
    }
    return 0;
}