結果
問題 |
No.409 ダイエット
|
ユーザー |
|
提出日時 | 2025-03-30 14:27:05 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 52 ms / 2,000 ms |
コード長 | 1,163 bytes |
コンパイル時間 | 1,962 ms |
コンパイル使用メモリ | 197,904 KB |
実行使用メモリ | 31,104 KB |
最終ジャッジ日時 | 2025-03-30 14:27:12 |
合計ジャッジ時間 | 7,276 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 92 |
ソースコード
#include<bits/stdc++.h> #define int __int128 using namespace std; using ld=long double; inline int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) { if(ch=='-')f=-1; ch=getchar(); } while(isdigit(ch)) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } inline void write(int x) { if(x<0) { putchar('-'); write(-x); return; } if(x>9)write(x/10); putchar(x%10+48); return; } int n,a,b,w,d[1000100],f[1000100],q[1000100],hd=1,tl=1; ld Y(int i){return f[i]+(i*(i+1))*b/2+i*a;} ld X(int i){return 1.0*i;} ld k(int i1,int i2){return (Y(i2)-Y(i1))/(X(i2)-X(i1));} signed main() { memset(f,0x3f,sizeof f); n=read(),a=read(),b=read(),w=read(); for(int i=1;i<=n;++i)d[i]=read(); f[0]=w; for(int i=1;i<=n;++i) { while(hd<tl&&k(q[hd],q[hd+1])<=i*b)++hd; f[i]=f[q[hd]]-(i-q[hd]-1)*a+d[i]+(i-q[hd]-1)*(i-q[hd])*b/2; while(hd<tl&&k(q[tl],i)<=k(q[tl],q[tl-1]))--tl; q[++tl]=i; } int ans=2e18; for(int i=n;~i;--i)ans=min(ans,f[i]-(n-i)*a+(n-i+1)*(n-i)*b/2); write(ans); return 0; }