Submission #130241

#	Time	Username	Problem	Language	Result	Execution time	Memory
130241		spookywooky	Split the sequence (APIO14_sequence)	C++14	0 / 100	2061 ms	63284 KiB

sequence

/**
 * Dont raise your voice, improve your argument.
 * --Desmond Tutu
 *
 *  https://oj.uz/problem/view/APIO14_sequence
 */

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#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);
        if(k==0) {
            vi empty;
            pllvi ret= { sum(i, j), empty };
            return ret;
        }

        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;
        }

        // k== k1 + k2 + 1
        pllvi ans;
        for(int k1=0, k2=k-1; k1<k; k1++, k2--) {
            /* 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;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29