Submission #106594

#	Time	Username	Problem	Language	Result	Execution time	Memory
106594		ekrem	Split the sequence (APIO14_sequence)	C++98	49 / 100	302 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 100005
using namespace std;

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

ll dp[N][205];
int git[N][205], pre[N], a[N], n, k, bas, son, j;
deque < pair < int , ii > > q;

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((int)q.size() >= 1 and d.st == q.back().nd.st){
		if(d.nd <= q.back().nd.nd)
			return;
		else
			son--;
	}
	while((int)q.size() >= 2){
		ii d1 = q.back().nd;
		pair < int, ii > t = q.back();
		q.pop_back();
		ii d2 = q.back().nd;
		q.push_back(t);
		if(kesisim(d, d2) <= kesisim(d1, d2))
			q.pop_back();
		else
			break;
	}
	q.push_back(mp(i, d));
}

ll bul(ll x){
	while((int)q.size() >= 2){
		ii d1 = q.front().nd;
		pair < int, ii > t = q.front();
		q.pop_front();
		ii d2 = q.front().nd;
		q.push_front(t);
		if(kesisim(d1, d2) <= x)
			q.pop_front();
		else
			break;
	}
	return q.front().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++){

		q.clear();

		ekle(0, mp(0, 0));
		for(int i = 1; i <= n; i++){
			j = bul(pre[i]);
			dp[i][x] = dp[j][x - 1] + 1ll*pre[j]*pre[i] - 1ll*pre[j]*pre[j];
			git[i][x] = j;
			ekle(i, mp(pre[i], dp[i][x - 1] - 1ll*pre[i]*pre[i]) );
		}
	}
	printf("%lld\n", dp[n][k]);
	son = n;
	bas = k;
	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:58: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:60:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",a + i);
   ~~~~~^~~~~~~~~~~~

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