Submission #373993

#	Time	Username	Problem	Language	Result	Execution time	Memory
373993		mariowong	Bigger segments (IZhO19_segments)	C++14	27 / 100	1594 ms	71020 KiB

segments

#include <bits/stdc++.h>
using namespace std;
 
long long n,a[3005],dp[3005][3005],ps[3005],ans;
int main(){
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i=1;i<=n;i++){
		cin >> a[i];
		ps[i]=ps[i-1]+a[i];
	}
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			dp[i][j]=1e18;
		}
	} 
	for (int i=1;i<=n;i++){
		dp[i][1]=ps[i];
		for (int j=2;j<=n;j++){
			for (int k=1;k<i;k++){
				if (dp[k][j-1] <= ps[i]-ps[k])
				dp[i][j]=min(dp[i][j],ps[i]-ps[k]);
			}
		}
	}
	for (int i=1;i<=n;i++){
		if (dp[n][i] != 1e18)
		ans=i;
	}
	cout << ans << "\n";
    return 0;
}	

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