제출 #1180585

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1180585		altern23	Bigger segments (IZhO19_segments)	C++20	100 / 100	57 ms	23892 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> in(N + 5), dp(N + 5);
		pii now = {INF, INF};
		for(int i = 1; i <= N; i++) dp[i] = {-1, ps[i]};
		for(int i = 1; i <= N; i++){
			now = min(now, in[i]);
			pii cur = {now.fi, ps[i] + now.sec};
			dp[i] = min(dp[i], cur);
			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){
				pii cur = {dp[i].fi - 1, -ps[i]};
				in[ans] = min(in[ans], 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: 36 / 36
• Subtask 5: 27 / 27