Submission #106576

#	Time	Username	Problem	Language	Result	Execution time	Memory
106576		ekrem	Split the sequence (APIO14_sequence)	C++98	60 / 100	162 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 n, k, bas, son, a[N], pre[N], dp[N][205], git[N][205];
pair < ll , ii > q[N];

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

void ekle(ll i, ii d){
	// if(d == mp(0ll, 0ll))
	// 	return;
	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){

	if(son - bas + 1 == 0)
		return 0;

	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("%lld %lld",&n ,&k);
	for(ll i = 1; i <= n; i++){
		scanf("%lld",a + i);
		pre[i] = pre[i - 1] + a[i];
	}
	for(ll x = 1; x <= k; x++){
		bas = 1, son = 0;
		ekle(1, mp(0, 0));
		for(ll i = 1; i <= n; i++){
			ll j = bul(pre[i]);
			dp[i][x] = max(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;
		}
	}
	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("%lld ", git[son][bas]);
		son = git[son][bas];
		bas--;
	}
	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld",&n ,&k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~
sequence.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",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