Submission #131437

#TimeUsernameProblemLanguageResultExecution timeMemory
131437someone_aaSplit the sequence (APIO14_sequence)C++17
0 / 100
363 ms131076 KiB
#include <bits/stdc++.h> #define ll long long #define pb push_back #define mp make_pair #define x real() #define y imag() #define pll pair<ll, ll> using namespace std; typedef long long ftype; typedef complex<ftype> point; const int maxn = 100100; ll arr[maxn], n, k; ll prefix[maxn], suffix[maxn]; ll dot(point a, point b) { return (a*conj(b)).x; } ll fx(point a, ll d) { return dot(a, {d, 1}); } ll dp[210][maxn]; ll dppntr[210][maxn]; class node { public: point f; ll lb, rb; node *lchild, *rchild; int ind; node(ll _lb, ll _rb) { lb = _lb; rb = _rb; lchild = rchild = NULL; f = {0, INT_MIN}; ind = 0; } void update(point nw, int _ind) { ll mid = (lb + rb) / 2; // SOMETHING NOT OKAY HERE bool lft = fx(nw, lb) > fx(f, lb); bool md = fx(nw, mid) > fx(f, mid); if(md) { swap(nw, f); swap(ind, _ind); } if(lb == rb) return; if(lft == md) { // they don't intersect in left, they might intersect in right part if(rchild == NULL) rchild = new node(mid+1, rb); rchild -> update(nw, _ind); } else { // they intersect in left part, continue searching in left if(lchild == NULL) lchild = new node(lb, mid); lchild -> update(nw, _ind); } } pll query(ll p) { ll mid = (lb + rb) / 2; if(lb == rb) return {fx(f, p), ind}; else { if(p <= mid) { pll val = {INT_MIN, INT_MIN}; if(lchild != NULL) val = lchild -> query(p); if(fx(f, p) > val.first) return {fx(f, p), ind}; else return val; } else { pll val = {INT_MIN, INT_MIN}; if(rchild != NULL) val = rchild -> query(p); if(fx(f, p) > val.first) return mp(fx(f, p), ind); else return val; } } } }; int main() { cin>>n>>k; for(int i=1;i<=n;i++) { cin>>arr[i]; prefix[i] = prefix[i-1] + arr[i]; } for(int i=n;i>=1;i--) { suffix[i] = suffix[i+1] + arr[i]; } for(int i=1;i<=n;i++) { dp[1][i] = prefix[i] * suffix[i+1]; } for(int p=2;p<=k;p++) { node *root = new node(0, 1e9); for(int i=1;i<=n;i++) { root -> update({-prefix[i-1], dp[p-1][i-1]}, i-1); if(i <= p + 1) { dp[p][i] = INT_MIN; continue; } pll qr = root -> query(suffix[i+1]); dp[p][i] = qr.first + prefix[i] * suffix[i+1]; dppntr[p][i] = qr.second; //root -> update({-prefix[i-1], dp[p-1][i-1]}, i-1); } /*for(int i=1;i<=n;i++) { for(int lst=i;lst>=1;lst--) { if(dp[p-1][lst-1] + (prefix[i] - prefix[lst-1]) * suffix[i+1] > dp[p][i]) { dp[p][i] = dp[p-1][lst-1] + (prefix[i] - prefix[lst-1]) * suffix[i+1]; dppntr[p][i] = lst-1; } } }*/ } ll result = 0LL; ll lst = 0; for(int i=1;i<n;i++) { if(dp[k][i] >= result) { result = dp[k][i]; lst = i; } } //lst++; //cout<<lst<<"\n"; vector<int>v; int p = k; while(lst > 0) { v.pb(lst); lst = dppntr[p][lst]; p--; } //reverse(v.begin(), v.end()); cout<<result<<"\n"; for(int i:v) { cout<<i<<" "; } cout<<"\n"; //cout<<"KRAJ: "<<v.size()<<"\n"; }
#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...