Submission #106588

#	Time	Username	Problem	Language	Result	Execution time	Memory
106588		ekrem	Split the sequence (APIO14_sequence)	C++98	60 / 100	171 ms	132096 KiB

sequence

#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define mod 1000000007
#define N 110005
using namespace std;

typedef long long ll;
typedef pair < ll , ll > ii;

ll pre[N], dp[N][305];
int git[N][305], a[N], n, k, bas, son;
pair < int , ii > q[N*10];

inline double kesisim(ii a, ii b){return 1.0 * ( b.nd - a.nd ) / (1.0 * (a.st - b.st) + 0.000000000000001) ;}

void ekle(ll i, ii d){
	if(son - bas + 1 >= 1 and d.st == q[son].nd.st){
		if(d.nd < q[son].nd.nd)
			return;
		else
			son--;
	}
	while(son - bas + 1 >= 2){
		ii d1 = q[son].nd;
		ii d2 = q[son - 1].nd;
		if(kesisim(d, d2) <= kesisim(d1, d2))
			son--;
		else
			break;
	}
	q[++son] = mp(i, d);
}

ll bul(ll x){
	while(son - bas + 1 >= 2){
		ii d1 = q[bas].nd;
		ii d2 = q[bas + 1].nd;
		if(kesisim(d1, d2) <= x)
			bas++;
		else
			break;
	}
	return q[bas].st;
}

int main() {
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	scanf("%d %d",&n ,&k);
	for(int i = 1; i <= n; i++){
		scanf("%d",a + i);
		pre[i] = pre[i - 1] + a[i];
	}
	for(int x = 1; x <= k; x++){
		bas = 1, son = 0;
		ekle(0, mp(0, 0));
		for(int i = 1; i <= n; i++){
			ll j = bul(pre[i]);
			dp[i][x] = dp[j][x - 1] + pre[j]*pre[i] - pre[j]*pre[j];
			git[i][x] = j;
			// for(ll j = 1; j < i; j++){
			// 	if(dp[j][x - 1] + pre[j]*pre[i] - pre[j]*pre[j] >= dp[i][x]){
			// 		dp[i][x] = dp[j][x - 1] + pre[j]*pre[i] - pre[j]*pre[j];
			// 		git[i][x] = j;
			// 	}
			// 	// dp[i][x] = max(dp[i][x], dp[j][x - 1] + pre[j]*pre[i] - pre[j]*pre[j]);
			// }
			// printf("dp[%lld][%lld] = %lld %lld\n", i, x, dp[i][x], j);
			// if(a[i] != 0)
			ekle(i, mp(pre[i], dp[i][x - 1] - pre[i]*pre[i]) );
			// cout << i << " -> " << pre[i] << " " << dp[i][x - 1] - pre[i]*pre[i] << " eklendi" << endl;
		}
		// cout << bas << " " << son << endl; 
	}
	printf("%lld\n", dp[n][k]);
	son = n;
	bas = k;
	// if(dp[n][k] == 0){
	// 	for(int i = 1; i <= k; i++)
	// 		printf("%d ", i);
	// 	return 0;
	// }
	for(ll i = 1; i <= k; i++){
		printf("%d ", git[son][bas]);
		son = git[son][bas];
		bas--;
	}
	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n ,&k);
  ~~~~~^~~~~~~~~~~~~~~~
sequence.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",a + i);
   ~~~~~^~~~~~~~~~~~

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