Submission #564975

#TimeUsernameProblemLanguageResultExecution timeMemory
564975ac2huSplit the sequence (APIO14_sequence)C++14
33 / 100
175 ms131072 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; struct Z{ vector<ll> vals; int n; Z(vector<int> &a){ n = a.size(); vals.resize(n , 0); vals[0] = a[0]; for(int i = 1;i<n;i++){ vals[i] = vals[i - 1] + a[i]; } } ll operator()(int l,int r){ if(l > r)return 0; assert(n > r); assert(l <= r); assert(l >= 0); int temp = vals[r]; if(l != 0)temp -= vals[l - 1]; return temp; } }; signed main(){ iostream::sync_with_stdio(false); cin.tie(nullptr);cout.tie(nullptr); int n, K;cin >> n >> K; vector<vector<vector<ll>>> dp(n, vector<vector<ll>>(n, vector<ll>(K + 2))); vector<vector<vector<int>>> spp(n, vector<vector<int>>(n, vector<int>(K + 2))); vector<int> a(n); for(auto &e : a)cin >> e; Z pref(a); auto solve = [&](auto &self, int l,int r,int k)->ll{ if(l > r)return 0; if(k == 0)return 0; if(dp[l][r][k] != 0)return dp[l][r][k]; assert(k > 0); ll ans = 0; for(int i = l;i<r;i++){ // (l, i), (l + 1, r) ll val = pref(l, i)*pref(i + 1, r) + self(self, l, i, 0) + self(self, i + 1, r, k - 1); if(val > ans){ spp[l][r][k] = i; ans = val; } } return (dp[l][r][k] = ans); }; vector<int> A; auto get = [&](auto &self,int l,int r,int k)->void{ if(l > r)return; if(k == 0)return; A.push_back(spp[l][r][k]); int i = spp[l][r][k]; self(self, l, i, 0); self(self, i + 1, r, k - 1); }; cout << solve(solve, 0, n - 1, K) << "\n"; get(get, 0, n - 1, K); for(auto e : A)cout << e + 1 << " "; cout << "\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...