Submission #887222

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

segments

#include <bits/stdc++.h>
using namespace std;
 
const int N = 3050;
long long a[N], pref[N], segment_count[N];
 
int main() {
	long long n;
	cin>>n;
	for(int i=1; i<=n; i++){
		cin>>a[i];
	}
	pref[1]=a[1];
	for(int i=2; i<=n; i++){
		pref[i]=pref[i-1]+a[i];
	}
	for(int i=1; i<=n; i++){
		for(int j=i+1; j<=n; j++){
			if(pref[j] - pref[i]>= a[i])segment_count[i]++;
		}
	}
	segment_count[n+1]=-1;
	long long ans=1, s=0, k=0;
	vector <long long> vec;
	for(int j=1; j<=n; j++){
		s=pref[j];
		ans=1;
		k=0;
		for(int i=j+1; i<=n; i++){
			k+=a[i];
			if(k >= s){
				if(segment_count[i] <= segment_count[i+1]){
					continue;
				}
				ans++;
				s=k;
				k=0;
			}
		}
		vec.push_back(ans);
	}
	sort(vec.begin(), vec.end());
	cout<<vec[(long long)vec.size()-1];
}

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