Submission #411647

#	Time	Username	Problem	Language	Result	Execution time	Memory
411647		antontsiorvas	Split the sequence (APIO14_sequence)	C++14	71 / 100	155 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];
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++){
		if(i <= 0 || i >= N) continue;
		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(trc_num != -1){
		dp[mid][k] = max_dp;
		trc[mid][k] = trc_num;
//	}
//	else{
//		dp[mid][k] = -900000000000000000;
//		trc[mid][k] = lo;
//	}
	
	
	divide_conquer(l,mid-1,lo,trc[mid][k],k);
	divide_conquer(mid+1,r,trc[mid][k],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:42:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |  scanf("%d%d",&N,&K);
      |  ~~~~~^~~~~~~~~~~~~~
sequence.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |   scanf("%lld",&data[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~

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