Submission #1209287

#TimeUsernameProblemLanguageResultExecution timeMemory
1209287Zbyszek99Split the sequence (APIO14_sequence)C++20
71 / 100
2095 ms82452 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ll long long #define ld long double #define ull unsigned long long #define ff first #define ss second #define pii pair<int,int> #define pll pair<long long, long long> #define vi vector<int> #define vl vector<long long> #define pb push_back #define rep(i, b) for(int i = 0; i < (b); ++i) #define rep2(i,a,b) for(int i = a; i <= (b); ++i) #define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c) #define count_bits(x) __builtin_popcountll((x)) #define all(x) (x).begin(),(x).end() #define siz(x) (int)(x).size() #define forall(it,x) for(auto& it:(x)) using namespace __gnu_pbds; using namespace std; typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; //mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());} //ll los(ll a, ll b) {return a + (mt() % (b-a+1));} const int INF = 1e9+50; const ll INF_L = 1e18+40; const ll MOD = 1e9+7; struct line { ll a,b,ind; ll operator()(ll x) { return a + b*x; } pll operator*(line& other) { return {other.a - a,b - other.b}; } }; deque<line> hull; ll arr[100001]; ll pref[100001]; void add_line(line l) { while(siz(hull) >= 2) { line l1 = hull.front(); hull.pop_front(); line l2 = hull.front(); hull.pop_front(); pll com = l1*l2; pll com2 = l1*l; if(com.ss < 0) { com.ff *= -1; com.ss *= -1; } if(com2.ss < 0) { com2.ff *= -1; com2.ss *= -1; } if(com.ff * com2.ss < com2.ff * com.ss && (com2.ss != 0 || l.b < l1.b)) { hull.push_front(l2); hull.push_front(l1); break; } else { hull.push_front(l2); } } if(siz(hull) == 0) { hull.push_front(l); } else { if(hull.front().b != l.b) { hull.push_front(l); } else { if(hull.front().a < l.a) { hull.pop_front(); hull.push_front(l); } } } if(siz(hull) == 2) { line l1 = hull.front(); hull.pop_front(); line l2 = hull.front(); hull.pop_front(); if(l1.b < l2.b) swap(l1,l2); hull.push_front(l2); hull.push_front(l1); } } pll get_best(ll x) { if(siz(hull) == 0) return {-1e18,-1}; while(siz(hull) >= 2) { line fl = hull.back(); hull.pop_back(); line f2 = hull.back(); hull.pop_back(); if(f2(x) >= fl(x)) { hull.push_back(f2); } else { hull.push_back(f2); hull.push_back(fl); break; } } return {hull.back()(x),hull.back().ind}; } ll dp[100001]; int best[100001][201]; void PrintHull() { vector<line> lines; while(!hull.empty()) { line l = hull.back(); hull.pop_back(); lines.pb(l); } forall(it,lines) hull.push_front(it); } int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); //random_start(); int n,k; cin >> n >> k; rep2(i,1,n) cin >> arr[i]; rep2(i,1,n) pref[i] = pref[i-1] + arr[i]; ll sum = 0; rep2(i,1,n) sum += arr[i]; rep(i,n+1) dp[i] = -1; dp[0] = 0; k++; rep(kk,k) { hull = {}; rep(i,n+1) { PrintHull(); ll prev_dp = dp[i]; pll b = get_best(pref[i]); dp[i] = -b.ff + pref[i] * pref[i]; if(b.ff == -1e18) dp[i] = -1; best[i][kk] = b.ss; if(prev_dp != -1) { add_line({-pref[i]*pref[i]-prev_dp,2*pref[i],i}); } } } cout << (sum*sum - dp[n])/2 << "\n"; vi ans; int z = k-1; int cur = n; rep(i,k-1) { ans.pb(best[cur][z]); cur = best[cur][z]; z--; } reverse(all(ans)); forall(it,ans) cout << it << " "; }
#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...