Submission #1055114

#TimeUsernameProblemLanguageResultExecution timeMemory
1055114underwaterkillerwhaleSplit the sequence (APIO14_sequence)C++17
60 / 100
2101 ms97016 KiB
#include <bits/stdc++.h> #define ll long long #define rep(i,m,n) for(int i=(m); i<=(n); i++) #define reb(i,m,n) for(int i=(m); i>=(n); i--) #define pii pair<int,int> #define pll pair<ll,ll> #define MP make_pair #define fs first #define se second #define bit(msk, i) ((msk >> i) & 1) #define iter(id, v) for(auto id : v) #define pb push_back #define SZ(v) (int)v.size() #define ALL(v) v.begin(),v.end() using namespace std; mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count()); ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); } const int N = 2e5 + 7; const int Mod = 1e9 + 7; const ll INF = 1e18; const ll BASE = 137; const int szBL = 320; int n, K; ll a[N]; ll dp[N][2]; map<int,int> trace[202]; ll pre[N]; struct Line { #define ld long double ll a, b, id; ld rx; Line(ll aa = 0, ll bb = 0, ll _id = INF, ld _rx = INF) : a(aa), b(bb), id(_id), rx(_rx) {}; ll eval(ll x) { return a * x + b; } ld isectx(const Line &other) { assert(a != other.a); return 1.0 * (other.b - b) / (a - other.a); } bool operator < (const Line &other) const { if (other.a != INF) return a < other.a; return rx < other.rx || (rx == other.rx && id < other.id); } }; struct dynamicCHT { set<Line> hull; void init () { set<Line> ().swap(hull); } bool hasPrev(set<Line>::iterator it) { return it != hull.begin(); } bool hasNext(set<Line>::iterator it) { return it != hull.end() && next(it) != hull.end(); } bool bad(Line l1, Line l2, Line l3) { return l2.isectx(l3) <= l1.isectx(l2); } bool bad(set<Line>::iterator it) { return (hasPrev(it) && hasNext(it) && bad(*prev(it), *it, *next(it))); } void calcrx(set<Line>::iterator it) { Line l = *it; if (hasNext(it)) l.rx = l.isectx(*next(it)); else l.rx = INF; hull.erase(it); hull.insert(l); } void insert_Line(Line newLine) { auto it = hull.lower_bound(newLine); if (it != hull.end() && it->a == newLine.a) { if (it->b > newLine.b) return; hull.erase(it); } it = hull.insert(newLine).first; if (bad(it)) { hull.erase(it); return; } while (hasPrev(it) && bad(prev(it))) hull.erase(prev(it)); while (hasNext(it) && bad(next(it))) hull.erase(next(it)); if (hasPrev(it)) calcrx(prev(it)); calcrx(it); } pll get (ll x) { if (hull.empty()) return MP(-INF, 0); Line it = *hull.lower_bound(Line(INF, 0, 0, x)); return MP(it.eval(x), it.id); } } cht; void solution () { cin >> n >> K; rep (i, 1, n) cin >> a[i]; rep (i, 1, n) pre[i] = pre[i - 1] + a[i]; rep (i, 1, n) dp[i][1] = 0; rep (k, 2, K) { cht.init(); rep (i, 1, n) { pll cur = cht.get(pre[i]); dp[i][k & 1] = cur.fs; if (cur.fs < 1e16) trace[k][i] = cur.se; // cout << i <<" "<<k<<" "<<cur.fs<<" "<<cur.se <<"\n"; cht.insert_Line(Line(pre[i], dp[i][k & 1 ^ 1] - pre[i] * pre[i], i)); } } ll res = 0; int opt = 0; rep (i, 1, n) { if (res < dp[i][K & 1] + (pre[n] - pre[i]) * pre[i]) { res = dp[i][K & 1] + (pre[n] - pre[i]) * pre[i]; opt = i; } } vector<int> Ans; reb (k, K, 1) { Ans.push_back(opt); opt = trace[k][opt]; } cout << res <<"\n"; iter (&id, Ans) cout << id<<" "; } #define file(name) freopen(name".inp","r",stdin); \ freopen(name".out","w",stdout); int main () { // file("TREEV"); ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0); int num_Test = 1; // cin >> num_Test; while (num_Test--) solution(); } /* no bug challenge +2 2 + 8 * 2 - 9 7 3 4 1 3 4 0 2 3 */

Compilation message (stderr)

sequence.cpp: In function 'void solution()':
sequence.cpp:116:50: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
  116 |             cht.insert_Line(Line(pre[i], dp[i][k & 1 ^ 1] - pre[i] * pre[i], i));
      |                                                ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...