Submission #173365

#	Time	Username	Problem	Language	Result	Execution time	Memory
173365		Abelyan	Bigger segments (IZhO19_segments)	C++17	100 / 100	124 ms	24864 KiB

segments

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
#define FOR(i,a) for (int i=0;i<(a);++i)
#define FORD(i,a) for (int i=(a)-1;i>=0;i--)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTD(i,b,a) for (int i=(b);i>=(a);--i)
#define trav(i,v) for (auto i : v)
#define all(v) v.begin(),v.end()
#define ad push_back
#define fr first
#define sc second
#define mpr(a,b) make_pair(a,b)
#define pir pair<int,int>
#define make_unique(v) v.erase(unique(all(v)),v.end())
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define srng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define y1 EsiHancagorcRepa
 
 
const int N=1e6+6;
const ll MOD=998244353;

ll dp1[N],dp2[N],a[N],pr[N],dn[N];
 
int main() {
	fastio;
	#ifdef ALEXPC
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	#endif
	int n;
	cin>>n;
	FORT(i,1,n){
		cin>>a[i];
		pr[i]=pr[i-1]+a[i];
	}
	ll tv=0;
	FORT(i,1,n){
		if (dn[i])tv=max(tv,dn[i]);
		dp1[i]=dp1[tv]+1;
		dp2[i]=pr[i]-pr[tv];
		dn[lower_bound(pr,pr+n+1,pr[i]+dp2[i])-pr]=i;
	}
	cout<<dp1[n]<<endl;
	return 0;
}

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