Submission #199528

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

sequence

#include <bits/stdc++.h>

#define MAXN 100100
#define MAXK 205
#define x real
#define y imag

using namespace std;

typedef long long int ll;
typedef complex<ll> point;
typedef pair<int, int> par;

ll dp[MAXN][MAXK], s[MAXN];
par _prev[MAXN][MAXK];
int n, k, arr[MAXN];
vector<point> hull, vecs;
vector<par> hull_ind;

ll cross(point va, point vb) {
	return va.x() * vb.y() - va.y() * vb.x();	
}

ll dot(point va, point vb) {
	return va.x() * vb.x() + va.y() * vb.y();
}

void add_line(pair<point, par> npp) {
	point np = npp.first;
	while (!vecs.empty() && dot(vecs.back(), np - vecs.back()) > 0) {
		vecs.pop_back();
		hull.pop_back();
		hull_ind.pop_back();
	}	
	if (!hull.empty()) {
		vecs.push_back(point(0, 1) * (np - hull.back()));
	}
	hull.push_back(np);
	hull_ind.push_back(npp.second);
}

ll query(ll thex, int i1, int i2) {
	point qp(thex, 1LL);
	auto it = lower_bound(vecs.begin(), vecs.end(), qp, [](point a, point b) {
		return cross(a, b) < 0;
	});
	_prev[i1][i2] = hull_ind[it-vecs.begin()];
	return dot(qp, hull[it-vecs.begin()]);
}

bool comp(pair<point, par> aa, pair<point, par> bb) {
	point a = aa.first, b = bb.first;
	return a.x() < b.x();	
}

void reset_hull() {
	vecs.clear(), hull.clear(), hull_ind.clear();
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> k;
	for (int _i = 1; _i <= n; _i++)
		cin >> arr[_i];
	s[0] = 0;
	for (int _i = 1; _i <= n; _i++)
		s[_i] = arr[_i] + s[_i-1];
	
	// dp[i][1] = s[i];
	for (int _i = 1; _i <= n; _i++)
		dp[_i][1] = s[_i];
	
	vector<pair<point, par> > toadd;
	
	for (int _i = 1; _i <= n; _i++)
		add_line(make_pair(point(s[_i], - s[_i] * s[_i]), par(_i, 1)));
	
	for (int j = 2; j <= k+1; j++) {
		for (int _i = j; _i <= n; _i++) {
			dp[_i][j] = query(s[_i], _i, j);
			toadd.push_back(make_pair(point(s[_i], dp[_i][j] - s[_i] * s[_i]), par(_i, j)));
		}
		reset_hull();
		sort(toadd.begin(), toadd.end(), comp);
		for (int _i = 0; _i < toadd.size(); _i++)
			add_line(toadd[_i]);
		toadd.clear();
	}
	
	cout << dp[n][k+1] << "\n";
	par p = _prev[n][k+1];
	vector<int> indexes;
	while (true) {
		indexes.push_back(p.first);
		if (p.second == 1)
			break;
		p = _prev[p.first][p.second];
	}
	for (int i = 0; i < indexes.size(); i++)
		if (i < indexes.size() - 1)
			cout << indexes[i] << " ";
		else
			cout << indexes[i] << "\n";
	/*ll manual_ans = 0;
	indexes.insert(indexes.begin(), n+1);
	for (int i = 1; i < indexes.size(); i++) {
		int ind = indexes[i];
		int final = indexes[i-1];
		// S[ind][final-1] * S[1][ind-1]
		manual_ans += (s[final-1] - s[ind-1]) * s[ind-1];
		cout << "I added S[" << ind <<  "][" << final-1 << "] * ";
		cout << "S[" << 1 << "][" << ind-1 << "] to the ans \n"; 
	}
	cout << manual_ans << "\n";*/
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:86:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int _i = 0; _i < toadd.size(); _i++)
                    ~~~^~~~~~~~~~~~~~
sequence.cpp:100:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < indexes.size(); i++)
                  ~~^~~~~~~~~~~~~~~~
sequence.cpp:101:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i < indexes.size() - 1)
       ~~^~~~~~~~~~~~~~~~~~~~

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