Submission #147150

#TimeUsernameProblemLanguageResultExecution timeMemory
147150jh05013Split the sequence (APIO14_sequence)C++17
100 / 100
1574 ms87096 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define entire(X) X.begin(),X.end() #define dbgv(V) for(auto x:V)cout<<x<<' ';cout<<endl; void OJize(){cin.tie(NULL); ios_base::sync_with_stdio(false);} template <typename T> struct CHT{ vector<tuple<T,T,int>> hull; int p=0; long double cr(int x){ auto [ax,bx,_] = hull[x]; auto [ay,by,__] = hull[x+1]; return (long double)(by-bx) / (ax-ay); } void insert(T a, T b, int i){ if(!hull.empty()){ auto [aa,bb,_] = hull.back(); if(aa == a && bb <= b) return; if(aa == a) hull.pop_back(); } hull.push_back({a,b,i}); while(hull.size() > 2 && cr(hull.size()-3) > cr(hull.size()-2)) hull.erase(hull.end()-2); } pair<T,int> get(T x){ while(p+1 < hull.size() && cr(p) <= x) p++; auto [a,b,i] = hull[p]; return {a*x + b, i}; } }; ll DP[2][100005], S[100005]; int prv[202][100005]; int main(){OJize(); int n, k; cin>>n>>k; k++; for(int i=0; i<n; i++){ ll x; cin>>x; S[i+1] = S[i] + x; } for(int j=2; j<=k; j++){ CHT<ll> cht; cht.insert(-S[j-1], S[j-1]*S[j-1]-DP[1-j%2][j-1], j-1); for(int i=j; i<=n; i++){ auto [val,idx] = cht.get(S[i]); DP[j%2][i] = -val, prv[j][i] = idx; cht.insert(-S[i], S[i]*S[i]-DP[1-j%2][i], i); } } cout << DP[k%2][n] << '\n'; vector<int> trace; int last = n; while(k >= 2){ last = prv[k--][last]; trace.push_back(last); } reverse(entire(trace)); dbgv(trace); }

Compilation message (stderr)

sequence.cpp: In instantiation of 'void CHT<T>::insert(T, T, int) [with T = long long int]':
sequence.cpp:45:62:   required from here
sequence.cpp:18:26: warning: unused variable '_' [-Wunused-variable]
             auto [aa,bb,_] = hull.back();
                          ^
sequence.cpp: In instantiation of 'std::pair<_BiIter, int> CHT<T>::get(T) [with T = long long int]':
sequence.cpp:47:42:   required from here
sequence.cpp:28:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(p+1 < hull.size() && cr(p) <= x) p++;
sequence.cpp: In instantiation of 'long double CHT<T>::cr(int) [with T = long long int]':
sequence.cpp:23:36:   required from 'void CHT<T>::insert(T, T, int) [with T = long long int]'
sequence.cpp:45:62:   required from here
sequence.cpp:12:22: warning: unused variable '_' [-Wunused-variable]
         auto [ax,bx,_] = hull[x]; auto [ay,by,__] = hull[x+1];
                      ^
sequence.cpp:12:49: warning: unused variable '__' [-Wunused-variable]
         auto [ax,bx,_] = hull[x]; auto [ay,by,__] = hull[x+1];
                                                 ^
#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...