Submission #1216059

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216059		elotelo966	Split the sequence (APIO14_sequence)	C++20	0 / 100	2095 ms	328 KiB

sequence

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

#define int long long
#define OYY LLONG_MAX
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fi first
#define se second
#define FOR for(int i=1;i<=n;i++)
#define mid (start+end)/2
#define pb push_back
#define lim 100005
//#define N 500050

typedef long long lo;

const int mod=1000000007;

int n,k;

int dizi[lim];

int tut[lim],ger[lim];

int cev=-1;

inline void f(int sira){
	if(sira>k){
		int cur_cev=0;
		vector<int> renk(n+1,0);
		int col=0;
		for(int i=1;i<=k;i++){
			int eski=renk[tut[i]];
			++col;
			int sum1=0,sum2=0;
			for(int j=1;j<=n;j++){
				if(eski==renk[j]){
					sum1+=dizi[j];
					renk[j]=col;
				}
				if(j==tut[i])break;
			}
			for(int j=tut[i]+1;j<=n;j++){
				if(eski==renk[j]){
					sum2+=dizi[j];
				}
			}
			cur_cev+=sum1*sum2;
			//~ if(tut[1]==1 && tut[2]==3 && tut[3]==5){
				//~ cout<<i<<" "<<k<<" "<<cur_cev<<	" "	<<sum1<<" "<<sum2<<endl;
			//~ }
		}
		if(cur_cev>cev){
			cev=cur_cev;
			for(int i=1;i<=k;i++)ger[i]=tut[i];
		}
		//~ cout<<cur_cev<<endl;
		//~ for(int i=1;i<=k;i++){
			//~ cout<<tut[i]<<" ";
		//~ }
		//~ cout<<endl;
		return ;
	}
	for(int i=1;i<=n;i++){
		int eski=tut[sira];
		tut[sira]=i;
		f(sira+1);
		tut[sira]=eski;
	}
}

int32_t main(){
	faster
	cin>>n>>k;
	
	FOR{
		cin>>dizi[i];
	}
	
	f(1);
	
	cout<<cev<<'\n';
	
	for(int i=1;i<=k;i++){
		cout<<ger[i]<<" ";
	}
	
	cout<<'\n';
	
	return 0;
}

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