Submission #1092542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092542		Sunbae	Bigger segments (IZhO19_segments)	C++17	100 / 100	72 ms	20900 KiB

segments

#include <bits/stdc++.h>
#define z exit(0)
#define mp make_pair
#define F first
#define S second
typedef long long ll;
using namespace std;
const ll INF = 1e15;
const int N = 5e5 + 5, inf = 1e8;
pair<int,ll> dp[N];
ll a[N], qs[N];
ll sum(int l, int r){ return qs[r] - ((l) ? qs[l-1] : 0);}
pair<int,ll> f(pair<int,ll> x, pair<int,ll> y){
	if((x.F > y.F) || (x.F == y.F && x.S <= y.S)) return x;
	return y;
}
signed main(){
	int n; scanf("%d", &n);
	for(int i = 0; i<n; ++i) scanf("%lld", a+i), qs[i] = a[i];
	for(int i = 1; i<n; ++i) qs[i] += qs[i-1];
	fill(dp, dp+n, mp(-inf, INF));
	dp[0] = {1, a[0]};
	for(int i = 1; i<n; ++i){
		if(a[i] >= dp[i-1].S){
			dp[i] = f(dp[i], mp(dp[i-1].F + 1, a[i]));
		}else{
			dp[i] = f(dp[i], mp(dp[i-1].F, dp[i-1].S + a[i]));
			int low = i+1, high = n-1, idx = -1;
			while(low <= high){
				int mid = low + ((high-low)>>1);
				if(sum(i, mid) >= dp[i-1].S) idx = mid, high = mid-1;
				else low = mid+1;
			}
			if(idx != -1) dp[idx] = f(dp[idx], mp(dp[i-1].F + 1, sum(i, idx)));
		}
	}
	printf("%d", dp[n-1].F);
}

Compilation message (stderr)

segments.cpp: In function 'int main()':
segments.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |  int n; scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
segments.cpp:19:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |  for(int i = 0; i<n; ++i) scanf("%lld", a+i), qs[i] = a[i];
      |                           ~~~~~^~~~~~~~~~~~~

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