該比賽已結束，您無法在比賽模式下遞交該題目。您可以點選“在題庫中開啟”以普通模式檢視和遞交本題。

Problem Description

Author: louishuang

nowob花費了7749天刻出了一個神奇演算法

可惜他太累了倒下去一直按到方向鍵跟空白鍵

code變成了這樣:

#include <iostre am>
#include <vect or>
#include <algori thm>

using name space st d;
typedef long lo ng ll;

const ll I NF = 2e18;
const int MA XN = 200005;
const int M AXC = 1000001;

struct L ine {
 ll k, b;
 int cn t;
 ll oper ator()(ll x) const { ret urn k * x + b; }
};

Li ne tr ee[MAXC * 4];

void up date(int p, int l, int r, Li ne v) {
 int m id = (l + r) >> 1;
 bool bl = (v(l) < tr ee[p](l)) || (v(l) == tr ee[p](l) && v.cn t > tre e[p].cnt);
 bool bm = (v(m id) < tre e[p](mid)) || (v(mi d) == tre e[p](mid) && v.cn t > tr ee[p].cnt);
 if (bm) sw ap(tre e[p], v);
 if (l == r) ret urn;
 if (bl != bm) up date(p << 1, l, mi d, v);
 else up date(p << 1 | 1, m id + 1, r, v);
}

Li ne qu ery(int p, int l, int r, ll x) {
 if (l == r) re turn tr ee[p];
 int mi d = (l + r) >> 1;
 Li ne re s = tre e[p];
 Li ne ne xt_res;
 if (x <= mi d) nex t_res = qu ery(p << 1, l, m id, x);
 else nex t_res = que ry(p << 1 | 1, m id + 1, r, x);
 if ((ne xt_res(x) < re s(x)) || (ne xt_res(x) == re s(x) && ne xt_res.cn t > re s.cnt)) {
 ret urn ne xt_res;
 } else {
 ret urn re s;
 }
}

ll d p[MAXN], s[MA XN];
int cn t[MAXN];

int ma in() {
 ios_base::sy nc_with_stdio(fal se);
 c in.t ie(NULL);
 int n;
 ll k;
 if (!(c in >> n >> k)) ret urn 0;
 vect or<ll> a(n + 1);
 for (int i = 1; i <= n; i++) ci n >> a[i];
 s[0] = 0;
 for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];

ll L = 0, R = 1e12, an s_val = 0;
 wh ile (L <= R) {
 ll mi d_cost = (L + R) / 2;
 for (int i = 0; i < MA XC * 4; i++) tr ee[i] = {0, I NF, 0};
 d p[0] = 0;
 cn t[0] = 0;
 up date(1, 0, MA XC, {0, 0, 0});
 for (int i = 1; i <= n; i++) {
 Li ne be st_line = qu ery(1, 0, MA XC, s[i]);
 d p[i] = be st_line(s[i]) + s[i] * s[i] + mi d_cost;
 cn t[i] = be st_line.cn t + 1;
 up date(1, 0, MA XC, {-2 * s[i], d p[i] + s[i] * s[i], cn t[i]});
 }
 if (cn t[n] >= k) {
 an s_val = d p[n] - k * mi d_cost;
 R = mi d_cost - 1;
 } else {
 L = mi d_cost + 1;
 }
 }
 co ut << an s_val << en dl;
 ret urn 0;
}

幫幫他找回原本的code吧太感謝了

只要直接送出正確的nowob就會給你一個AC感謝你