Submission #1180581

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180581		altern23	Bigger segments (IZhO19_segments)	C++20	37 / 100	1593 ms	3400 KiB

segments

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const int MAXN = 1e6;
const ll INF = 4e18;
const int MOD = 998244353;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int tc = 1;	
	// cin >> tc;		
	for(;tc--;){
		ll N; cin >> N;
		vector<ll> a(N + 5), ps(N + 5);
		for(int i = 1; i <= N; i++){
			cin >> a[i];
			ps[i] = ps[i - 1] + a[i];
		}
		vector<pii> dp(N + 5);
		for(int i = 1; i <= N; i++) dp[i] = {-1, ps[i]};
		for(int i = 1; i <= N; i++){
			ll lf = i + 1, rg = N, ans = -1;
			for(;lf <= rg;){
				ll mid = (lf + rg) / 2;
				if(ps[mid] - ps[i] >= dp[i].sec){
					ans = mid;
					rg = mid - 1;
				}
				else lf = mid + 1;
			}
			if(ans != -1){
				for(int j = ans; j <= N; j++){
					pii cur = {dp[i].fi - 1, ps[j] - ps[i]};
					dp[j] = min(dp[j], cur);
				}
			}
		}

		cout << -dp[N].fi << "\n";
	}
}

/*
1 2 3 4 5 6 7
*/
 

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