Submission #863029

#	Time	Username	Problem	Language	Result	Execution time	Memory
863029		LePhiPhat	Bigger segments (IZhO19_segments)	C++17	0 / 100	0 ms	348 KiB

segments

// https://codeforces.com/blog/entry/64479?#comment-484350
#include <iostream>
#include <cstdint>
#include <string>
#include <vector>

using namespace std;

#ifdef DEBUG 
#include "debuge.cpp"
#else
#define debug(...) 42
#endif

typedef            long long ll;
typedef       pair<int, int>  pii;
typedef         pair<ll, ll>  pll;
typedef pair<double, double> pdd;
typedef          vector<int>  vi;
typedef           vector<ll>  vll;
typedef          vector<pii>  vii;

#define                   fi  first
#define                   se  second
#define               all(v)  (v).begin(), (v).end()
#define                SZ(x)  ((int) (x).size())
#define                   pb  push_back
#define                   pf  push_front
#define                   lb  lower_bound
#define                   ub  upper_bound
 
#define         FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define         ROF(i, a, b) for (int i = (a); i > (b); --i)


void LPP(int &test)  {
	int n;
	cin >> n;
	vll a(n + 1), p(n + 1);
	vector<vi> dp(n + 1, vi(n + 1, -1));
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) p[i] = p[i - 1] + a[i];
	dp[0][0] = 0;
	// subtask 2
//	for (int i = 1; i <= n; i++) {
//		for (int j = 1; j <= i; j++) {
//			for (int k = i; k >= j; k--) if (dp[k - 1][j - 1] != -1) {
//				int r = k - 1, l = dp[k - 1][j - 1];
//				ll lst = p[r] - p[l];
//				ll now = p[i] - p[r];
//				if (now >= lst) {
//					dp[i][j] = max(dp[i][j], (k - 1) * 1ll);; 
//				}
//			}
//		}
//	}
	// subtask 3
	for (int i = 1; i <= n; i++) dp[i][1] = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j < n; j++) if (dp[i][j] != -1) {
			int l = dp[i][j];
			int r = i;
			if (p[r] - p[l] > p[n] - p[i]) {
				continue;
			}
			int lo = i, hi = n + 1;
			while (lo + 1 < hi) {
				int mi = (lo + hi) / 2;
				if (p[mi] - p[i] >= p[r] - p[l]) 
					hi = mi;
				else 
					lo = mi;
			}
			dp[hi][j + 1] = max(dp[hi][j + 1], i);
		}
	}
	int ans = 1;
	FOR(j, 0, n + 1) {
		if (dp[n][j] != -1) ans = max(ans, j);
	}
	cout << ans;
}

int32_t main() {
	cin.tie(0) -> ios::sync_with_stdio(false);
	int tc = 1;
	// cin >> tc;
	for (int i = 1; i <= tc; i++) LPP(i);
}






































/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
*/

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