Submission #524598

#	Time	Username	Problem	Language	Result	Execution time	Memory
524598		Mr_Husanboy	Bigger segments (IZhO19_segments)	C++14	100 / 100	80 ms	20920 KiB

segments

// Muallif: Mansuraliyev Husanboy Murotali o'g'li  >> NamPS

#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define ios ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define all(a) a.begin(), a.end()
#define F first
#define S second
// 0-9 >> 48-57;    A-Z>>65-90   and   a-z>>97-122 respectively;	

//string a[11]={"CARS","cars","IuVEJxTXs","UvOHhng","yZKfAYmaqolM","NtGQibw","djPrCpek","FWzL","aySBaPyb","RM","gzYMynY"};
//string b[11]={"Unil","EPFL","vpVZzBNtL","SCubWma","ocIYneAPqxDs","hRkMGgJ","fHrFUQTj","XOwd","PolyProg","is","awesome"};



void solve(){
	int n; cin>>n;
	ll a[n+1];for(int i=1;i<=n;i++) cin>>a[i];
	vector<ll> sum(n+2); ll k=0;
	for(int i=1;i<=n;i++) k+=a[i],sum[i]=k;
	vector<ll> dp(n+2),tem(n+2);
	for(int i=1;i<=n;i++){
		tem[i]=max(tem[i],tem[i-1]);
		dp[i]=dp[tem[i]]+1;ll o=2ll*sum[i]-sum[tem[i]];
		int x=lower_bound(sum.begin()+1,sum.end()-1,o)-sum.begin();
		tem[x]=max(i*1ll,tem[x]);
	}
	cout<<dp[n];
}


int main(){
	ios; 
	//int t=1;   cin>>t; while(t--)
	solve();
}

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