# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
147150 | jh05013 | Split the sequence (APIO14_sequence) | C++17 | 1574 ms | 87096 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |