Submission #411213

#	Time	Username	Problem	Language	Result	Execution time	Memory
411213		antontsiorvas	Split the sequence (APIO14_sequence)	C++14	21 / 100	118 ms	131076 KiB

sequence

#include <cstdio>
#include <algorithm>
#include <utility>
#include <vector>
#define lli long long int
using namespace std;

int N, K, trc[100005][206];
lli data[100005], prefix[100005], dp[100005][206];
lli inf = -90000000000000;
vector<int> ans;

void divide_conquer(int l, int r, int lo, int hi, int k){
	if(l > r) return;
	
	int mid = (l+r)/2, trc_num = -1;
	lli max_dp = -1;
	
	for(int i=lo; i<=min(mid-1,hi); i++){
		lli temp_num = dp[i][k-1] + prefix[i]*(prefix[mid]-prefix[i]);
		if(max_dp < temp_num){
			max_dp = temp_num;
			trc_num = i;
		}
	}
	
	if(max_dp < 0) return;
	
	dp[mid][k] = max_dp;
	trc[mid][k] = trc_num;
	
	divide_conquer(l,mid-1,lo,trc_num,k);
	divide_conquer(mid+1,r,trc_num,hi,k);
}

int main(){
	scanf("%d%d",&N,&K);
	
	for(int i=1; i<=N; i++){
		scanf("%lld",&data[i]);
		prefix[i] = prefix[i-1] + data[i];
	}
	
	for(int k=1; k<=K; k++) divide_conquer(1,N,1,N,k);
	
	printf("%lld\n",dp[N][K]);
	int trc_num = N;
	for(int i=K; i>0; i--){
		ans.push_back(trc[trc_num][i]);
		trc_num = trc[trc_num][i];
	}
	for(int i=K-1; i>=0; i--) printf("%d ",ans[i]);
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |  scanf("%d%d",&N,&K);
      |  ~~~~~^~~~~~~~~~~~~~
sequence.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |   scanf("%lld",&data[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~

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