|
| 1 | +#include <bits/stdc++.h> |
| 2 | +using namespace std; |
| 3 | + |
| 4 | +using ll = long long; |
| 5 | +using db = long double; // or double, if TL is tight |
| 6 | +using str = string; // yay python! |
| 7 | + |
| 8 | +// pairs |
| 9 | +using pi = pair<int,int>; |
| 10 | +using pl = pair<ll,ll>; |
| 11 | +using pd = pair<db,db>; |
| 12 | +#define mp make_pair |
| 13 | +#define f first |
| 14 | +#define s second |
| 15 | + |
| 16 | +#define tcT template<class T |
| 17 | +#define tcTU tcT, class U |
| 18 | +// ^ lol this makes everything look weird but I'll try it |
| 19 | +tcT> using V = vector<T>; |
| 20 | +tcT, size_t SZ> using AR = array<T,SZ>; |
| 21 | +using vi = V<int>; |
| 22 | +using vb = V<bool>; |
| 23 | +using vl = V<ll>; |
| 24 | +using vd = V<db>; |
| 25 | +using vs = V<str>; |
| 26 | + |
| 27 | + |
| 28 | + |
| 29 | + |
| 30 | +// vectors |
| 31 | +// oops size(x), rbegin(x), rend(x) need C++17 |
| 32 | +#define sz(x) int((x).size()) |
| 33 | +#define bg(x) begin(x) |
| 34 | +#define all(x) bg(x), end(x) |
| 35 | +#define rall(x) x.rbegin(), x.rend() |
| 36 | +#define sor(x) sort(all(x)) |
| 37 | +#define rsz resize |
| 38 | +#define ins insert |
| 39 | +#define pb push_back |
| 40 | +#define eb emplace_back |
| 41 | +#define ft front() |
| 42 | +#define bk back() |
| 43 | + |
| 44 | +#define lb lower_bound |
| 45 | +#define ub upper_bound |
| 46 | +tcT> int lwb(V<T>& a, const T& b) { return int(lb(all(a),b)-bg(a)); } |
| 47 | +tcT> int upb(V<T>& a, const T& b) { return int(ub(all(a),b)-bg(a)); } |
| 48 | + |
| 49 | +// loops |
| 50 | +#define FOR(i,a,b) for (int i = (a); i < (b); ++i) |
| 51 | +#define F0R(i,a) FOR(i,0,a) |
| 52 | +#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i) |
| 53 | +#define R0F(i,a) ROF(i,0,a) |
| 54 | +#define rep(a) F0R(_,a) |
| 55 | +#define each(a,x) for (auto& a: x) |
| 56 | + |
| 57 | +const int MOD = 1e9+7; // 998244353; |
| 58 | +const int MX = 2e5+5; |
| 59 | +const ll BIG = 1e18; // not too close to LLONG_MAX |
| 60 | +const db PI = acos((db)-1); |
| 61 | +const int dx[4]{1,0,-1,0}, dy[4]{0,1,0,-1}; // for every grid problem!! |
| 62 | +mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); |
| 63 | +template<class T> using pqg = priority_queue<T,vector<T>,greater<T>>; |
| 64 | + |
| 65 | +// bitwise ops |
| 66 | +// also see https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html |
| 67 | +constexpr int pct(int x) { return __builtin_popcount(x); } // # of bits set |
| 68 | +constexpr int bits(int x) { // assert(x >= 0); // make C++11 compatible until USACO updates ... |
| 69 | + return x == 0 ? 0 : 31-__builtin_clz(x); } // floor(log2(x)) |
| 70 | +constexpr int p2(int x) { return 1<<x; } |
| 71 | +constexpr int msk2(int x) { return p2(x)-1; } |
| 72 | + |
| 73 | +ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up |
| 74 | +ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down |
| 75 | + |
| 76 | +tcT> bool ckmin(T& a, const T& b) { |
| 77 | + return b < a ? a = b, 1 : 0; } // set a = min(a,b) |
| 78 | +tcT> bool ckmax(T& a, const T& b) { |
| 79 | + return a < b ? a = b, 1 : 0; } // set a = max(a,b) |
| 80 | + |
| 81 | +tcTU> T fstTrue(T lo, T hi, U f) { |
| 82 | + ++hi; assert(lo <= hi); // assuming f is increasing |
| 83 | + while (lo < hi) { // find first index such that f is true |
| 84 | + T mid = lo+(hi-lo)/2; |
| 85 | + f(mid) ? hi = mid : lo = mid+1; |
| 86 | + } |
| 87 | + return lo; |
| 88 | +} |
| 89 | +tcTU> T lstTrue(T lo, T hi, U f) { |
| 90 | + --lo; assert(lo <= hi); // assuming f is decreasing |
| 91 | + while (lo < hi) { // find first index such that f is true |
| 92 | + T mid = lo+(hi-lo+1)/2; |
| 93 | + f(mid) ? lo = mid : hi = mid-1; |
| 94 | + } |
| 95 | + return lo; |
| 96 | +} |
| 97 | +tcT> void remDup(vector<T>& v) { // sort and remove duplicates |
| 98 | + sort(all(v)); v.erase(unique(all(v)),end(v)); } |
| 99 | +tcTU> void erase(T& t, const U& u) { // don't erase |
| 100 | + auto it = t.find(u); assert(it != end(t)); |
| 101 | + t.erase(it); } // element that doesn't exist from (multi)set |
| 102 | + |
| 103 | +#define tcTUU tcT, class ...U |
| 104 | + |
| 105 | +inline namespace Helpers { |
| 106 | + //////////// is_iterable |
| 107 | + // https://stackoverflow.com/questions/13830158/check-if-a-variable-type-is-iterable |
| 108 | + // this gets used only when we can call begin() and end() on that type |
| 109 | + tcT, class = void> struct is_iterable : false_type {}; |
| 110 | + tcT> struct is_iterable<T, void_t<decltype(begin(declval<T>())), |
| 111 | + decltype(end(declval<T>())) |
| 112 | + > |
| 113 | + > : true_type {}; |
| 114 | + tcT> constexpr bool is_iterable_v = is_iterable<T>::value; |
| 115 | + |
| 116 | + //////////// is_readable |
| 117 | + tcT, class = void> struct is_readable : false_type {}; |
| 118 | + tcT> struct is_readable<T, |
| 119 | + typename std::enable_if_t< |
| 120 | + is_same_v<decltype(cin >> declval<T&>()), istream&> |
| 121 | + > |
| 122 | + > : true_type {}; |
| 123 | + tcT> constexpr bool is_readable_v = is_readable<T>::value; |
| 124 | + |
| 125 | + //////////// is_printable |
| 126 | + // // https://nafe.es/posts/2020-02-29-is-printable/ |
| 127 | + tcT, class = void> struct is_printable : false_type {}; |
| 128 | + tcT> struct is_printable<T, |
| 129 | + typename std::enable_if_t< |
| 130 | + is_same_v<decltype(cout << declval<T>()), ostream&> |
| 131 | + > |
| 132 | + > : true_type {}; |
| 133 | + tcT> constexpr bool is_printable_v = is_printable<T>::value; |
| 134 | +} |
| 135 | + |
| 136 | +inline namespace Input { |
| 137 | + tcT> constexpr bool needs_input_v = !is_readable_v<T> && is_iterable_v<T>; |
| 138 | + tcTUU> void re(T& t, U&... u); |
| 139 | + tcTU> void re(pair<T,U>& p); // pairs |
| 140 | + |
| 141 | + // re: read |
| 142 | + tcT> typename enable_if<is_readable_v<T>,void>::type re(T& x) { cin >> x; } // default |
| 143 | + tcT> void re(complex<T>& c) { T a,b; re(a,b); c = {a,b}; } // complex |
| 144 | + tcT> typename enable_if<needs_input_v<T>,void>::type re(T& i); // ex. vectors, arrays |
| 145 | + tcTU> void re(pair<T,U>& p) { re(p.f,p.s); } |
| 146 | + tcT> typename enable_if<needs_input_v<T>,void>::type re(T& i) { |
| 147 | + each(x,i) re(x); } |
| 148 | + tcTUU> void re(T& t, U&... u) { re(t); re(u...); } // read multiple |
| 149 | + |
| 150 | + // rv: resize and read vectors |
| 151 | + void rv(size_t) {} |
| 152 | + tcTUU> void rv(size_t N, V<T>& t, U&... u); |
| 153 | + template<class...U> void rv(size_t, size_t N2, U&... u); |
| 154 | + tcTUU> void rv(size_t N, V<T>& t, U&... u) { |
| 155 | + t.rsz(N); re(t); |
| 156 | + rv(N,u...); } |
| 157 | + template<class...U> void rv(size_t, size_t N2, U&... u) { |
| 158 | + rv(N2,u...); } |
| 159 | + |
| 160 | + // dumb shortcuts to read in ints |
| 161 | + void decrement() {} // subtract one from each |
| 162 | + tcTUU> void decrement(T& t, U&... u) { --t; decrement(u...); } |
| 163 | + #define ints(...) int __VA_ARGS__; re(__VA_ARGS__); |
| 164 | + #define int1(...) ints(__VA_ARGS__); decrement(__VA_ARGS__); |
| 165 | +} |
| 166 | + |
| 167 | +inline namespace ToString { |
| 168 | + tcT> constexpr bool needs_output_v = !is_printable_v<T> && is_iterable_v<T>; |
| 169 | + |
| 170 | + // ts: string representation to print |
| 171 | + tcT> typename enable_if<is_printable_v<T>,str>::type ts(T v) { |
| 172 | + stringstream ss; ss << fixed << setprecision(15) << v; |
| 173 | + return ss.str(); } // default |
| 174 | + tcT> str bit_vec(T t) { // bit vector to string |
| 175 | + str res = "{"; F0R(i,sz(t)) res += ts(t[i]); |
| 176 | + res += "}"; return res; } |
| 177 | + str ts(V<bool> v) { return bit_vec(v); } |
| 178 | + template<size_t SZ> str ts(bitset<SZ> b) { return bit_vec(b); } // bit vector |
| 179 | + tcTU> str ts(pair<T,U> p); // pairs |
| 180 | + tcT> typename enable_if<needs_output_v<T>,str>::type ts(T v); // vectors, arrays |
| 181 | + tcTU> str ts(pair<T,U> p) { return "("+ts(p.f)+", "+ts(p.s)+")"; } |
| 182 | + tcT> typename enable_if<is_iterable_v<T>,str>::type ts_sep(T v, str sep) { |
| 183 | + // convert container to string w/ separator sep |
| 184 | + bool fst = 1; str res = ""; |
| 185 | + for (const auto& x: v) { |
| 186 | + if (!fst) res += sep; |
| 187 | + fst = 0; res += ts(x); |
| 188 | + } |
| 189 | + return res; |
| 190 | + } |
| 191 | + tcT> typename enable_if<needs_output_v<T>,str>::type ts(T v) { |
| 192 | + return "{"+ts_sep(v,", ")+"}"; } |
| 193 | + |
| 194 | + // for nested DS |
| 195 | + template<int, class T> typename enable_if<!needs_output_v<T>,vs>::type |
| 196 | + ts_lev(const T& v) { return {ts(v)}; } |
| 197 | + template<int lev, class T> typename enable_if<needs_output_v<T>,vs>::type |
| 198 | + ts_lev(const T& v) { |
| 199 | + if (lev == 0 || !sz(v)) return {ts(v)}; |
| 200 | + vs res; |
| 201 | + for (const auto& t: v) { |
| 202 | + if (sz(res)) res.bk += ","; |
| 203 | + vs tmp = ts_lev<lev-1>(t); |
| 204 | + res.ins(end(res),all(tmp)); |
| 205 | + } |
| 206 | + F0R(i,sz(res)) { |
| 207 | + str bef = " "; if (i == 0) bef = "{"; |
| 208 | + res[i] = bef+res[i]; |
| 209 | + } |
| 210 | + res.bk += "}"; |
| 211 | + return res; |
| 212 | + } |
| 213 | +} |
| 214 | + |
| 215 | +inline namespace Output { |
| 216 | + template<class T> void pr_sep(ostream& os, str, const T& t) { os << ts(t); } |
| 217 | + template<class T, class... U> void pr_sep(ostream& os, str sep, const T& t, const U&... u) { |
| 218 | + pr_sep(os,sep,t); os << sep; pr_sep(os,sep,u...); } |
| 219 | + // print w/ no spaces |
| 220 | + template<class ...T> void pr(const T&... t) { pr_sep(cout,"",t...); } |
| 221 | + // print w/ spaces, end with newline |
| 222 | + void ps() { cout << "\n"; } |
| 223 | + template<class ...T> void ps(const T&... t) { pr_sep(cout," ",t...); ps(); } |
| 224 | + // debug to cerr |
| 225 | + template<class ...T> void dbg_out(const T&... t) { |
| 226 | + pr_sep(cerr," | ",t...); cerr << endl; } |
| 227 | + void loc_info(int line, str names) { |
| 228 | + cerr << "Line(" << line << ") -> [" << names << "]: "; } |
| 229 | + template<int lev, class T> void dbgl_out(const T& t) { |
| 230 | + cerr << "\n\n" << ts_sep(ts_lev<lev>(t),"\n") << "\n" << endl; } |
| 231 | + #ifdef LOCAL |
| 232 | + #define dbg(...) loc_info(__LINE__,#__VA_ARGS__), dbg_out(__VA_ARGS__) |
| 233 | + #define dbgl(lev,x) loc_info(__LINE__,#x), dbgl_out<lev>(x) |
| 234 | + #else // don't actually submit with this |
| 235 | + #define dbg(...) 0 |
| 236 | + #define dbgl(lev,x) 0 |
| 237 | + #endif |
| 238 | + |
| 239 | + const clock_t beg = clock(); |
| 240 | + #define dbg_time() dbg((db)(clock()-beg)/CLOCKS_PER_SEC) |
| 241 | +} |
| 242 | + |
| 243 | +inline namespace FileIO { |
| 244 | + void setIn(str s) { freopen(s.c_str(),"r",stdin); } |
| 245 | + void setOut(str s) { freopen(s.c_str(),"w",stdout); } |
| 246 | + void setIO(str s = "") { |
| 247 | + cin.tie(0)->sync_with_stdio(0); // unsync C / C++ I/O streams |
| 248 | + // cin.exceptions(cin.failbit); |
| 249 | + // throws exception when do smth illegal |
| 250 | + // ex. try to read letter into int |
| 251 | + if (sz(s)) setIn(s+".in"), setOut(s+".out"); // for old USACO |
| 252 | + } |
| 253 | +} |
| 254 | + |
| 255 | +/** |
| 256 | + * Description: Add lines of the form $ax+b$, |
| 257 | + * query maximum $y$-coordinate for any $x$. |
| 258 | + * Time: O(\log N) |
| 259 | + * Source: KACTL |
| 260 | + * https://github.com/kth-competitive-programming/kactl/commit/165807e28402c9be906f6e6a09452431787bb70d?diff=unified |
| 261 | + * Verification: https://judge.yosupo.jp/problem/line_add_get_min |
| 262 | + */ |
| 263 | + |
| 264 | +using T = ll; const T INF = LLONG_MAX; // a/b rounded down |
| 265 | +// ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } |
| 266 | + |
| 267 | +bool _Q = 0; |
| 268 | +struct Line { |
| 269 | + T a, b; mutable T lst; |
| 270 | + /// friend str ts(const Line& L) { return ts(vl{L.a,L.b,L.lst}); } |
| 271 | + T eval(T x) const { return a*x+b; } |
| 272 | + bool operator<(const Line&o)const{return _Q?lst<o.lst:a<o.a;} |
| 273 | + T last_gre(const Line& o) const { assert(a <= o.a); |
| 274 | + // greatest x s.t. a*x+b >= o.a*x+o.b |
| 275 | + return lst=(a==o.a?(b>=o.b?INF:-INF):fdiv(b-o.b,o.a-a));} |
| 276 | +}; |
| 277 | + |
| 278 | +struct LineContainer: multiset<Line> { |
| 279 | + bool isect(iterator it) { auto n_it = next(it); |
| 280 | + if (n_it == end()) return it->lst = INF, 0; |
| 281 | + return it->last_gre(*n_it) >= n_it->lst; } |
| 282 | + void add(T a, T b) { // remove lines after |
| 283 | + auto it = ins({a,b,0}); while (isect(it)) erase(next(it)); |
| 284 | + if (it == begin()) return; |
| 285 | + if (isect(--it)) erase(next(it)), isect(it); |
| 286 | + while (it != begin()) { // remove lines before |
| 287 | + --it; if (it->lst < next(it)->lst) break; |
| 288 | + erase(next(it)); isect(it); } |
| 289 | + } |
| 290 | + T qmax(T x) { assert(!empty()); |
| 291 | + _Q = 1; T res = lb({0,0,x})->eval(x); _Q = 0; |
| 292 | + return res; } |
| 293 | +}; |
| 294 | + |
| 295 | +struct LCdeque : deque<Line> { |
| 296 | + void addBack(Line L) { // assume nonempty |
| 297 | + while (1) { |
| 298 | + auto a = bk; pop_back(); a.lst = a.last_gre(L); |
| 299 | + if (size() && bk.lst >= a.lst) continue; |
| 300 | + pb(a); break; |
| 301 | + } |
| 302 | + L.lst = INF; pb(L); |
| 303 | + } |
| 304 | + void addFront(Line L) { |
| 305 | + while (1) { |
| 306 | + if (!size()) { L.lst = INF; break; } |
| 307 | + if ((L.lst = L.last_gre(ft)) >= ft.lst) pop_front(); |
| 308 | + else break; |
| 309 | + } |
| 310 | + push_front(L); |
| 311 | + } |
| 312 | + void add(T a, T b) { // line goes to one end of deque |
| 313 | + a *= -1, b *= -1; |
| 314 | + if (!size() || a <= ft.a) addFront({a,b,0}); |
| 315 | + else assert(a >= bk.a), addBack({a,b,0}); |
| 316 | + } |
| 317 | + int ord = 0; // 1 = x's come in increasing order, -1 = decreasing order |
| 318 | + T query(T x) { |
| 319 | + assert(ord); |
| 320 | + if (ord == 1) { |
| 321 | + while (ft.lst < x) pop_front(); |
| 322 | + return -ft.eval(x); |
| 323 | + } else { |
| 324 | + while(size()>1&&prev(prev(end()))->lst>=x)pop_back(); |
| 325 | + return -bk.eval(x); |
| 326 | + } |
| 327 | + } |
| 328 | +}; |
| 329 | + |
| 330 | + |
| 331 | +int n,k; |
| 332 | +ll ans = INF; |
| 333 | +vi r; |
| 334 | +ll dp[1001],pre[1001],PRE[1001]; |
| 335 | + |
| 336 | +void upd() { |
| 337 | + LCdeque L; |
| 338 | + L.ord = 1; |
| 339 | + F0R(i,n+1) { |
| 340 | + if (dp[i] != MOD) L.add(-pre[i],dp[i]+PRE[i]); |
| 341 | + dp[i] = L.query(i)+i*pre[i]-PRE[i]; |
| 342 | + } |
| 343 | +} |
| 344 | + |
| 345 | +int main() { |
| 346 | + // setIO("cbarn"); |
| 347 | + re(n,k); r.rsz(n); re(r); ckmin(k,n); |
| 348 | + reverse(all(r)); |
| 349 | + F0R(i,n) { |
| 350 | + FOR(j,1,n+1) { |
| 351 | + pre[j] = pre[j-1]+r[j-1]; |
| 352 | + PRE[j] = PRE[j-1]+j*r[j-1]; |
| 353 | + } |
| 354 | + F0R(j,n+1) dp[j] = MOD; |
| 355 | + dp[0] = 0; F0R(j,k) upd(); |
| 356 | + ckmin(ans,dp[n]); |
| 357 | + rotate(begin(r),begin(r)+1,end(r)); |
| 358 | + } |
| 359 | + ps(ans); |
| 360 | + // you should actually read the stuff at the bottom |
| 361 | +} |
| 362 | + |
| 363 | +/* stuff you should look for |
| 364 | + * int overflow, array bounds |
| 365 | + * special cases (n=1?), slow multiset operations |
| 366 | + * do smth instead of nothing and stay organized |
| 367 | +*/ |
0 commit comments