Submission #683209

#	Time	Username	Problem	Language	Result	Execution time	Memory
683209		Markomafko972	Split the sequence (APIO14_sequence)	C++14	71 / 100	354 ms	131072 KiB

sequence

#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define pii pair<int, int>
typedef long long ll;
using namespace std;

const int MOD = 1e9 + 7;
const ll INF = 1e18;
const int OFF = (1 << 20);

int n, k;
int a[100005];
ll p[100005];
ll dp[100005][205];
int gdje[100005][205];
vector< pair<int, int> > v;

void rek(int x, int y) {
	if (y == 0) return;
	
	cout << x << " ";
	
	rek(gdje[x][y], y-1);
}

int ccw(pair<ll, ll> p1, pair<ll, ll> p2, pair<ll, ll> p3) {
	ll out = p1.X * (p2.Y - p3.Y) + p2.X * (p3.Y - p1.Y) + p3.X * (p1.Y - p2.Y);
	if (out > 0) return 1;
	if (out == 0) return 0;
	if (out < 0) return -1;
}


pair<ll, ll> cord(int x, int y) {
	return {p[x], dp[x][y]-p[x]*p[x]};
}

ll val(int x, int y, ll tren) {
	return dp[x][y]-p[x]*p[x]+p[x]*tren;
}

void dodaj(int x, int y) {
	if (v.size() == 0) {
		v.push_back({x, y});
		return;
	}
	
	pair<int, int> z = v.back();
	v.pop_back();
	
	while ((int)v.size() > 0 && ccw(cord(v.back().X, v.back().Y), cord(z.X, z.Y), cord(x, y)) >= 0) {
		z = v.back();
		v.pop_back();
	}
	
	v.push_back(z);
	v.push_back({x, y});
}

int query(int pref) {
	
	int lo = 0, hi = (int)v.size()-2;
	while (lo < hi) {
		int mid = (lo + hi) / 2;
		if (val(v[mid].X, v[mid].Y, pref) < val(v[mid+1].X, v[mid+1].Y, pref)) lo = mid+1;
		else hi = mid;
	}
	
	if (val(v[lo].X, v[lo].Y, pref) < val(v[lo+1].X, v[lo+1].Y, pref)) return v[lo+1].X;
	return v[lo].X;
}

int main () {

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		p[i] = p[i-1] + a[i];
	}
	
	
	for (int i = 2; i <= k+1; i++) {
		for (int j = 1; j <= n; j++) {
			if (dp[j][i-1] != -INF) dodaj(j, i-1);
		}
		
		for (int j = 1; j <= n; j++) {
			int pos = query(p[j]);
			pos = min(pos, j-1);			
			gdje[j][i] = pos;
			if (dp[pos][i-1] == -INF) dp[j][i] = -INF;
			else dp[j][i] = val(pos, i-1, p[j]);
			
			if (pos < 1) dp[j][i] = -INF;
		}
		
		v.clear();
	}
	
	cout << dp[n][k+1] << "\n";
	rek(gdje[n][k+1], k);

	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int ccw(std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::pair<long long int, long long int>)':
sequence.cpp:33:1: warning: control reaches end of non-void function [-Wreturn-type]
   33 | }
      | ^

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