Submission #1101677

#TimeUsernameProblemLanguageResultExecution timeMemory
1101677HuyATSplit the sequence (APIO14_sequence)C++14
100 / 100
498 ms84776 KiB
#include<bits/stdc++.h> #define newl '\n' const int N = 1e5 + 10; const int K = 2e2 + 10; const int V = 1e7 + 10; const long long INF = 1e18; const long long M = 1e9 + 7; struct Line{ long long a,b,it; long long operator ()(long long x){ return a * x + b; } long long intersect(const Line &rhs) const { if(a == rhs.a){ // std::cout << -1; exit(0); } long long nume = b - rhs.b; long long denom = rhs.a - a; return nume / denom; } }; long long a[N + 1],s[N + 1],n,k; int trace[K + 1][N + 1]; void readData(){ std::cin >> n >> k; for(int i = 1;i <= n;++i){ std::cin >> a[i]; s[i] = s[i - 1] + a[i]; } } ///(s[r] - s[l]) * (s[n] - s[r]) ///(s[r] * s[n] - s[r] * s[r] - s[l] * s[n] + s[l] * s[r] + f[l] ///-s[r] * s[r] //meh not important ///s[r] * s[n] // also not important ///-s[l] * s[n] + s[l] * s[r] = -s[l] * s[n] + -s[l] * -s[r],-s[l] = a,(s[n] - s[r]) = x ///f[l] = b void brute(){ std::vector<long long> pr(n + 1,0); int it = 0; for(int i = 1;i <= k;++i){ std::vector<long long> f(n + 1,0); for(int j = 1;j < n;++j){ trace[i][j] = j - 1; for(int j1 = j - 1;j1 >= 0;--j1){ long long t = (s[j] - s[j1]) * (s[n] - s[j]) + pr[j1]; if(t > f[j]){ f[j] = t; trace[i][j] = j1; } if(f[j] >= f[it]){ it = j; } } // if(i == 3 && j == 5){ // std::cout << f[j] << newl; // } } pr.swap(f); } std::cout << pr[it] << newl; int t = k; while(t > 0){ std::cout << it << " "; it = trace[t--][it]; } } bool dominate(const Line &l,const Line &o,const Line &o1){ // if(l.a == o.a && l.b == o.b){ // return true; // } ///line lhs dominate line o // if(l.a == o.a){ // return (l.b >= o.b); // } long long inter = l.intersect(o); long long inter1 = o.intersect(o1); return inter >= inter1; } void solve(){ long long it = 0; std::deque<Line> dq; std::vector<long long> pr(n + 1,0); for(int i = 1;i <= k;++i){ std::vector<long long> f(n + 1,0); for(int j = 0;j <= n;++j){ if(j > 0 && j < n){ long long x = s[n] - s[j]; while((int)dq.size() >= 2 && dq.end()[-1](x) <= dq.end()[-2](x)){ dq.pop_back(); } f[j] = dq.end()[-1](x) + s[j] * x; trace[i][j] = dq.end()[-1].it; // if(i == 3 && j == 5){ // std::cerr << "IMP " << f[j] << newl; // } if(f[j] >= f[it]){ it = j; } // if(f[j] < f[j - 1] && s[j] == s[j - 1]){ // exit(0); // } // std::cout << f[j] << " "; } Line cur = {-s[j],pr[j],j}; while((int)dq.size() > 0){ if(cur.a == dq[0].a){ if((int)cur.b >= dq[0].b){ dq.pop_front(); continue; } }else if((int)dq.size() > 1 && dominate(cur,dq[0],dq[1])){ dq.pop_front(); continue; } break; } if((int)dq.size() == 0 || cur.a != dq[0].a){ dq.push_front(cur); } } dq.clear(); pr.swap(f); } std::cout << pr[it] << newl; int t = k; while(t > 0){ std::cout << it << " "; it = trace[t--][it]; } } int main(){ std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr);std::cout.tie(nullptr); readData(); solve(); return 0; }
#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...