#include <bits/stdc++.h> #define task "testing" #define ll long long #define multitest 0 using namespace std; struct Node { ll res, pre, suf, sm; int resl, resr, prer, sufl, l, r; }; const int N = 3e5; bool lz[4*N+5]; Node mx[4*N+5], mn[4*N+5]; Node merge(Node u, Node v) { Node res; res.sm = u.sm+v.sm, res.l = u.l, res.r = v.r; res.pre = max(u.pre, u.sm+v.pre); if (res.pre == u.pre) { res.prer = u.prer; } else { res.prer = v.prer; } res.suf = max(u.suf+v.sm, v.suf); if (res.suf == v.suf) { res.sufl = v.sufl; } else { res.sufl = u.sufl; } res.res = max({u.res, v.res, u.suf+v.pre}); if (res.res == u.res) { res.resl = u.resl, res.resr = u.resr; } else if (res.res == v.res) { res.resl = v.resl, res.resr = v.resr; } else { res.resl = u.sufl, res.resr = v.prer; } return res; } void push(int nd, int lf, int rt) { if (lz[nd]) { swap(mx[nd], mn[nd]); if (lf != rt) { lz[nd*2] ^= lz[nd], lz[nd*2+1] ^= lz[nd]; } lz[nd] = 0; } } void upd(int nd, int lf, int rt, int p, ll v) { if (p < lf || rt < p) return; if (lf == rt) { mx[nd].sm = v, mx[nd].l = mx[nd].r = p; if (v >= 0) { mx[nd].res = mx[nd].pre = mx[nd].suf = v; mx[nd].resl = mx[nd].resr = mx[nd].prer = mx[nd].sufl = p; } else { mx[nd].res = mx[nd].pre = mx[nd].suf = 0; mx[nd].resl = mx[nd].resr = mx[nd].prer = mx[nd].sufl = -1; } mn[nd].sm = -v, mn[nd].l = mn[nd].r = p; if (v <= 0) { mn[nd].res = mn[nd].pre = mn[nd].suf = -v; mn[nd].resl = mn[nd].resr = mn[nd].prer = mn[nd].sufl = p; } else { mn[nd].res = mn[nd].pre = mn[nd].suf = 0; mn[nd].resl = mn[nd].resr = mn[nd].prer = mn[nd].sufl = -1; } return; } int mid = (lf+rt)/2; upd(nd*2, lf, mid, p, v); upd(nd*2+1, mid+1, rt, p, v); mx[nd] = merge(mx[nd*2], mx[nd*2+1]); mn[nd] = merge(mn[nd*2], mn[nd*2+1]); } void flip(int nd, int lf, int rt, int l, int r) { push(nd, lf, rt); if (r < lf || rt < l) return; if (l <= lf && rt <= r) { swap(mx[nd], mn[nd]); if (lf != rt) { lz[nd*2] ^= 1, lz[nd*2+1] ^= 1; } return; } int mid = (lf+rt)/2; flip(nd*2, lf, mid, l, r); flip(nd*2+1, mid+1, rt, l, r); mx[nd] = merge(mx[nd*2], mx[nd*2+1]); mn[nd] = merge(mn[nd*2], mn[nd*2+1]); } void flo(int ID) { int n, m; cin >> n >> m; for (int x = 1; x <= n; x++) { ll v; cin >> v; upd(1, 1, n, x, v); } ll ans = 0, s = 0; while (m--) { ans = max(ans, s += mx[1].res); flip(1, 1, n, mx[1].resl, mx[1].resr); } cout << ans << "\n"; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } int TCS = 1, ID = 1; if (multitest) { cin >> TCS; } while (TCS--) flo(ID++); return 0; }

feast.cpp: In function 'int main()':
feast.cpp:160:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  160 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
feast.cpp:161:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  161 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~