Submission #976707

#	Time	Username	Problem	Language	Result	Execution time	Memory
976707		tamir1	Split the sequence (APIO14_sequence)	C++17	11 / 100	2065 ms	604 KiB

sequence

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,k,i,a[101],b[11],sum[101],s,ans=-1;
vector<ll> v;
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> k;
	for(i=1;i<=n;i++){
		cin >> a[i];
		sum[i]=sum[i-1]+a[i];
	}
	for(i=1;i<n;i++) b[i]=i;
	b[0]=0;
	do{
		s=0;
		for(i=1;i<=k;i++){
			if(b[i]>b[i+1] && i<k){
				s=-1;
				break;
			}
			s+=((sum[b[i]]-sum[b[i-1]])*(sum[n]-sum[b[i]]));
		}
		if(s>ans){
			ans=s;
			v.clear();
			for(i=1;i<=k;i++) v.push_back(b[i]);
		}
	}while(next_permutation(b+1,b+n));
	cout << ans << "\n";
	for(i=0;i<k;i++) cout << v[i] << " ";
}

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