Submission #863354

#	Time	Username	Problem	Language	Result	Execution time	Memory
863354		When_Brain_Ded	Bigger segments (IZhO19_segments)	C++14	13 / 100	0 ms	348 KiB

segments

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
using namespace std;

typedef tree<int,null_type,less<int>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set;
#define iset indexed_set
#define ll long long int
#define ull unsigned long long int
#define f first
#define sec second
#define rep(i, st, end) for(ll i = st; i < end; i++)
const ll mod = 1e9 + 7;
using ii = pair<ll,ll>;

void solve()
{
	ll n; cin>>n;
	
	ll a[n];
	rep(i,0,n) {
		cin>>a[i];
	}

	vector<ll> dp(n), pre(n), last(n);
	rep(i,0,n) {
		pre[i] = a[i];
		if(i) {
			pre[i] += pre[i-1];
		}
		dp[i] = 1;
		last[i] = pre[i];
	}

	rep(i,1,n) {
		ll low = 0, high = i-1, ans = -1;
		while(high >= low) {
			ll mid = (high + low)/2;
			if(pre[mid]+last[mid] <= pre[i]) {
				ans = mid;
				low = mid+1;
			}
			else {
				high = mid-1;
			}
		}
		if(ans != -1) {
			dp[i] = dp[ans] + 1;
			last[i] = pre[i] - pre[ans];
		}
	}
	cout<<dp[n-1];
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    //int t; cin>>t; while(t--)
    solve();
    return 0;
}

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