Submission #630521

#	Time	Username	Problem	Language	Result	Execution time	Memory
630521		duytuandao21	Bigger segments (IZhO19_segments)	C++17	100 / 100	80 ms	16876 KiB

segments

#include<iostream>
#include<cmath>
#include<string.h>
#include<algorithm>
#include<stack>
#include<queue>
#include<deque>
using namespace std;
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define fi first
#define se second
#define ll long long
#define mp make_pair
#define pb push_back
#define ii pair<int, int>
#define task "test" 

const int inf = 1e9 + 7;
const ll infll = (ll)1e18 + 7;
const int MOD = 1e9 + 7;
const int N = 2e6 + 3;

template <typename T1, typename T2> bool minimize(T1 &a, T2 b){if (a > b) {a = b; return true;} return false;}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b){if (a < b) {a = b; return true;} return false;}

int n; 
ll a[N], dp[N], lef[N];

int get(int l,int r,int i) {
	ll S = a[i] - a[lef[i]];
	int ans = -1;
	while(l <= r) {
		int mid = (l + r) / 2; 
		ll sum = a[mid] - a[i];
		if(sum >= S) {
			ans = mid;
			r = mid - 1;
		} else l = mid + 1;
	}
	return ans;
}
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) {
		cin>>a[i];
		a[i] += a[i-1];
	}
	for(int i=1;i<=n;i++) {
		maximize(lef[i], lef[i-1]);
		dp[i] = dp[lef[i]] + 1;
		int pos = get(i+1,n,i);
		if(pos != -1) maximize(lef[pos], i);
	}
	cout<<dp[n];
	return 0;
}

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