Submission #800267

#	Time	Username	Problem	Language	Result	Execution time	Memory
800267		vjudge1	Bigger segments (IZhO19_segments)	C++17	0 / 100	1 ms	340 KiB

segments

#include <bits/stdc++.h>
using namespace std;

const int maxn = 303;
int n;
int a[maxn];
long long p[maxn];
bool dp[maxn][maxn];
int ans;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for (int i=0; i<n; i++) cin >> a[i];

	p[0] = 0;
	for (int i=1; i<=n; i++) p[i] = p[i-1] + a[i-1];

	memset(dp, false, sizeof dp);
	dp[0][0] = true;
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=n; j++) {
			for (int k=0; k<i; k++) {
				if (j * p[k] <= (j-1) * p[i]) dp[i][j] |= dp[k][j-1];
			}
		}
	}

	ans = 0;
	for (int i=1; i<=n; i++) {
		if (dp[n][i]) ans = i;
	}

	cout << ans << '\n';

	return 0;
}

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