Submission #1181640

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181640		nuutsnoynton	Bigger segments (IZhO19_segments)	C++20	27 / 100	1599 ms	70984 KiB

segments

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
ll dp[3003][3003], a[3002], pre[3002];

ll Sum(ll x, ll y) {
	return pre[y] - pre[x - 1];
}

int main() {
	ll n, m, s, sum, r, x, y, i, j, ans, t, cnt;

	cin >> n;
	
	
	pre[0] = 0;
	for (i = 1; i <= n; i ++) {
		cin >> a[i];
		pre[i] = pre[i - 1] + a[i];
	}
	for (i = 1; i <= n; i ++) for (j = 1; j<= n; j ++) dp[i][j] = 1e18;
	s =a[1];
	ans = 1;
	dp[1][1] = a[1];
	for (i = 2; i <= n; i ++) {
		s += a[i];
		dp[i][1] = s;
		for ( r = 1; r < i; r ++) {
			for (j = 1; j < n; j ++) {
				if ( dp[r][j] <= Sum(r + 1, i)) {
					dp[i][j + 1] = Sum(r + 1, i);
				}
			}
		}
	}
	
	ans =0 ;
	for (i = 1; i <= n; i ++) {
		for (j = 1; j <= n; j ++) {
			if ( dp[i][j] != 1e18) ans = max(ans, j);
		}
	}
	cout << ans << endl;
}

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