Submission #501126

#	Time	Username	Problem	Language	Result	Execution time	Memory
501126		NachoLibre	Bigger segments (IZhO19_segments)	C++17	100 / 100	69 ms	13000 KiB

segments

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
using namespace std;

const int N = 500005;
int n, b[N][2];
ll a[N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for(int i = 1; i <= n; ++i) {
		cin >> a[i];
		a[i] += a[i - 1];
	} a[n + 1] = 1e17;
	b[1][0] = 1; b[1][1] = 0;
	int x = 0, y = 0;
	for(int i = 1; i <= n; ++i) {
		if(b[i][0] >= x) { x = b[i][0]; y = max(b[i][1], y); }
		int l = i + 1, r = n + 1;
		while(l < r) {
			int m = l + r >> 1;
			if(a[m] - a[i] >= a[i] - a[y]) r = m;
			else l = m + 1;
		}
		if(x + 1 >= b[l][0]) { b[l][0] = x + 1; b[l][1] = i; }
		// cout << i << " " << x << " " << y << endl;
	}
	cout << x << endl;
	return 0;
}

Compilation message (stderr)

segments.cpp: In function 'int main()':
segments.cpp:26:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |    int m = l + r >> 1;
      |            ~~^~~

• Subtask 1: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 10 / 10
• Subtask 4: 36 / 36
• Subtask 5: 27 / 27