# 笨蛋花的小窝qwq

“我要再和生活死磕几年。要么我就毁灭，要么我就注定铸就辉煌。如果有一天，你发现我在平庸面前低了头，请向我开炮。”

### 题解 P6246 【[IOI2000] 邮局 加强版】

posted on 2020-04-01 08:00:50 | under 题解 |

int tp ;
ll res ;
ll f[N] ;
ll sum[N] ;
int lrg[N] ;
int cnt[N] ;
int stk[N] ;
int base[N] ;
int n, m, k ;

using IPT::qr;
using IPT::qra;
using IPT::qrs;
using IPT::qrdb;
using OPT::qw;
using OPT::qwa;
using OPT::qws;

il ll calc(int l, int r){
ll h = (l + r + 1) / 2 ;
ll ret = sum[r] - sum[h] ;
ll d1 = 1ll * (h - l) * base[h] ;
ll d2 = 1ll * (r - h) * base[h] ;
return ret - d2 + d1 - sum[h] + sum[l] ;
}
il ll trans(ll p, ll x){
return f[p] + calc(p, x) ;
}
bool check(ll x){
stk[tp = 0] = 0 ;
int h = 0 ; lrg[0] = 1 ;
for (int i = 1 ; i <= n ; ++ i){
while (h < tp && lrg[h] < i)
++ h ; if (lrg[h] > i) -- h ;
f[i] = trans(stk[h], i) + x, cnt[i] = cnt[stk[h]] + 1 ;
while (tp && trans(stk[tp], lrg[tp]) >= trans(i, lrg[tp]))
stk[tp] = 0, lrg[tp] = n + 1, -- tp ;
int l = lrg[tp], r = n, mid, ans = n + 1 ;
while (l <= r){
int mid = (l + r) >> 1 ;
if (trans(stk[tp], mid) >= trans(i, mid))
ans = mid, r = mid - 1 ; else l = mid + 1 ;
}
if (ans <= n) stk[++ tp] = i, lrg[tp] = ans ;
}
res = f[n] - x * m ; return (bool)(cnt[n] < m) ;
}
int main(){
qr(n) ; qr(m) ;
for (int i = 1 ; i <= n ; ++ i)
qr(base[i]), sum[i] = sum[i - 1] + (ll)base[i] ;
ll l = 0, r = 1e9, mid, ans ;
lrg[0] = 1 ; sum[n + 1] = sum[n] ;
while (l <= r){
mid = (l + r) >> 1 ;
if (check(mid)) r = mid - 1 ;
else ans = mid, l = mid + 1 ;
}
check(ans) ; qw(res) ; return 0 ;
}

#