| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 130232 | spookywooky | Split the sequence (APIO14_sequence) | C++14 | 0 ms | 0 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.
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set;
typedef long long ll;
//typedef __int128 lll;
#define fori(n) for(ll i=0; i<(n); i++)
typedef pair<int, int> pii;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
int main() {
cin.tie(nullptr);
std::ios::sync_with_stdio(false);
int n, K;
cin>>n>>K;
vi a(n);
vll pra(n+1);
fori(n) {
cin>>a[i];
pra[i+1]=pra[i]+a[i];
}
typedef tuple<int, int, int> ti3;
typedef pair<ll, vi> pllvi;
map<ti3, pllvi> dp;
/* dp[(i, j, k)]= largest number (and sequence of indexes) you can get with seq
* starting at i, of len j, with k recursions. j>k
*/
function<ll(int, int)> sum=[&](int i, int j) {
return pra[i+j]-pra[i];
};
function<pllvi(int, int, int)> calc=[&](int i, int j, int k) {
assert(j>k);
assert(k>0);
//if(k==0)
// return 0LL;
auto it=dp.find({i,j,k});
if(it!=dp.end())
return it->second;
if(k==1) {
ll lans=0;
int ansIdx=-1;
for(int l=1; l<j; l++) {
ll val=sum(i, l)*sum(i+l, j-l);
if(val>=lans) {
lans=val;
ansIdx=i+l;
}
}
pllvi ans={ lans, vi({ ansIdx })};
dp[{i,j,k}]=ans;
return ans;
}
pllvi ans;
for(int k1=1; k1<k-1; k1++) {
int k2=k-k1-1;
/* parts must be at least size of kx+1 */
for(int l=k1+1; j-l>k2; l++) {
ll points=sum(i,l)*sum(i+l, j-l);
pllvi valL=calc(i, l, k1);
pllvi valR=calc(i+l, j-l, k2);
ll lsum=valL.first+valR.first+points;
if(lsum>=ans.first) {
vi path(valL.second);
for(int idx : valR.second)
path.push_back(idx);
path.push_back(i+l);
ans={ lsum, path };
}
}
}
dp[{i,j,k}]=ans;
return ans;
};
auto ans=calc(0, n, K);
cout<<ans.first<<endl;
for(auto idx : ans.second)
cout<<idx<<" ";
cout<<endl;
}