Submission #477448

#	Time	Username	Problem	Language	Result	Execution time	Memory
477448		PiejanVDC	Split the sequence (APIO14_sequence)	C++17	0 / 100	2085 ms	8648 KiB

sequence

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

int n,k;
int64_t ans;
vector<int>pref(100005);
vector<int>v,ans_v;

void dfs(int i, int last_cut, int cnt, int64_t curr) {
    if(cnt == k) {
        if(curr > ans)
            ans_v = v;
        ans=max(ans,curr);
        return;
    }
    if(i == n)
        return;
    dfs(i+1,last_cut,cnt,curr);
    if(i>0) {
        v.push_back(i);
        dfs(i+1,i,cnt+1,curr + (pref[n] - pref[i]) * (pref[i] - pref[last_cut]));
        v.pop_back();
    }
}

signed main() {
    cin>>n>>k;
    pref[0]=0;
    for(int i = 0 ; i < n ; i++) {
        int x; cin>>x;
        pref[i+1] = pref[i] + x;
    }
    dfs(0,0,0,0);
    cout << ans << "\n";
    for(auto z : ans_v)
        cout << ++z << " ";
}

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