Submission #48014

#	Time	Username	Problem	Language	Result	Execution time	Memory
48014		square1001	Split the sequence (APIO14_sequence)	C++14	100 / 100	595 ms	83544 KiB

sequence

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const long long inf = 1LL << 60;
int n, m, c, s[100009], sp[100009], ss[100009], d[100009], p[209][100009]; long long dp[100009], ndp[100009];
bool comp(long long xa, long long xb, long long ya, long long yb) {
	// judge if xa * xb >= ya * yb
	int xa1 = xa >> 31, xa0 = xa & ((1 << 31) - 1);
	int xb1 = xb >> 31, xb0 = xb & ((1 << 31) - 1);
	int ya1 = ya >> 31, ya0 = ya & ((1 << 31) - 1);
	int yb1 = yb >> 31, yb0 = yb & ((1 << 31) - 1);
	long long xc3 = 0;
	long long xc2 = 1LL * xa1 * xb1;
	long long xc1 = 1LL * xa1 * xb0 + 1LL * xa0 * xb1;
	long long xc0 = 1LL * xa0 * xb0;
	long long yc3 = 0;
	long long yc2 = 1LL * ya1 * yb1;
	long long yc1 = 1LL * ya1 * yb0 + 1LL * ya0 * yb1;
	long long yc0 = 1LL * ya0 * yb0;
	xc1 += xc0 >> 31; xc0 &= ((1 << 31) - 1);
	xc2 += xc1 >> 31; xc1 &= ((1 << 31) - 1);
	xc3 += xc2 >> 31; xc2 &= ((1 << 31) - 1);
	yc1 += yc0 >> 31; yc0 &= ((1 << 31) - 1);
	yc2 += yc1 >> 31; yc1 &= ((1 << 31) - 1);
	yc3 += yc2 >> 31; yc2 &= ((1 << 31) - 1);
	if (xc3 != yc3) return xc3 > yc3;
	if (xc2 != yc2) return xc2 > yc2;
	if (xc1 != yc1) return xc1 > yc1;
	return xc0 >= yc0;
}
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 0; i < n; ++i) {
		cin >> ss[i + 1];
		ss[i + 1] += ss[i];
	}
	int rn = 0;
	for (int i = 0; i < n; i++) {
		if (ss[i + 1] != ss[i]) {
			s[++rn] = ss[i + 1];
			sp[rn] = i + 1;
		}
	}
	fill(dp + 1, dp + n + 1, inf);
	for (int i = 0; i <= m && i < rn; ++i) {
		c = 0;
		for (int j = 0; j <= rn; ++j) {
			while (c >= 2 && comp(s[j] - s[d[c - 1]], dp[d[c - 1]] - dp[d[c - 2]], s[d[c - 1]] - s[d[c - 2]], dp[j] - dp[d[c - 1]])) {
				c--;
			}
			d[c++] = j;
		}
		int ptr = 0;
		for (int j = 0; j <= rn; ++j) {
			while (ptr + 1 != c && d[ptr + 1] < j && dp[d[ptr]] - 2LL * s[j] * s[d[ptr]] > dp[d[ptr + 1]] - 2LL * s[j] * s[d[ptr + 1]]) ptr++;
			ndp[j] = dp[d[ptr]] + 2LL * (s[j] - s[d[ptr]]) * s[j];
			p[i][j] = d[ptr];
		}
		copy(ndp, ndp + rn + 1, dp);
	}
	cout << 1LL * s[rn] * s[rn] - dp[rn] / 2 << '\n';
	int pos = rn;
	vector<int> ret;
	for (int i = min(m, rn - 1); i >= 1; --i) {
		pos = p[i][pos];
		ret.push_back(sp[pos]);
	}
	for (int i = 1; i <= n; i++) {
		if (ss[i] == ss[i - 1] && ret.size() != m) {
			ret.push_back(i);
		}
	}
	for (int i = 0; i < ret.size(); i++) {
		cout << ret[i];
		if (i + 1 == ret.size()) cout << '\n';
		else cout << ' ';
	}
	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'bool comp(long long int, long long int, long long int, long long int)':
sequence.cpp:9:44: warning: integer overflow in expression [-Woverflow]
  int xa1 = xa >> 31, xa0 = xa & ((1 << 31) - 1);
                                  ~~~~~~~~~~^~~
sequence.cpp:10:44: warning: integer overflow in expression [-Woverflow]
  int xb1 = xb >> 31, xb0 = xb & ((1 << 31) - 1);
                                  ~~~~~~~~~~^~~
sequence.cpp:11:44: warning: integer overflow in expression [-Woverflow]
  int ya1 = ya >> 31, ya0 = ya & ((1 << 31) - 1);
                                  ~~~~~~~~~~^~~
sequence.cpp:12:44: warning: integer overflow in expression [-Woverflow]
  int yb1 = yb >> 31, yb0 = yb & ((1 << 31) - 1);
                                  ~~~~~~~~~~^~~
sequence.cpp:21:38: warning: integer overflow in expression [-Woverflow]
  xc1 += xc0 >> 31; xc0 &= ((1 << 31) - 1);
                            ~~~~~~~~~~^~~
sequence.cpp:22:38: warning: integer overflow in expression [-Woverflow]
  xc2 += xc1 >> 31; xc1 &= ((1 << 31) - 1);
                            ~~~~~~~~~~^~~
sequence.cpp:23:38: warning: integer overflow in expression [-Woverflow]
  xc3 += xc2 >> 31; xc2 &= ((1 << 31) - 1);
                            ~~~~~~~~~~^~~
sequence.cpp:24:38: warning: integer overflow in expression [-Woverflow]
  yc1 += yc0 >> 31; yc0 &= ((1 << 31) - 1);
                            ~~~~~~~~~~^~~
sequence.cpp:25:38: warning: integer overflow in expression [-Woverflow]
  yc2 += yc1 >> 31; yc1 &= ((1 << 31) - 1);
                            ~~~~~~~~~~^~~
sequence.cpp:26:38: warning: integer overflow in expression [-Woverflow]
  yc3 += yc2 >> 31; yc2 &= ((1 << 31) - 1);
                            ~~~~~~~~~~^~~
sequence.cpp: In function 'int main()':
sequence.cpp:72:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (ss[i] == ss[i - 1] && ret.size() != m) {
                             ~~~~~~~~~~~^~~~
sequence.cpp:76:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ret.size(); i++) {
                  ~~^~~~~~~~~~~~
sequence.cpp:78:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i + 1 == ret.size()) cout << '\n';
       ~~~~~~^~~~~~~~~~~~~

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