제출 #863086

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
863086		LePhiPhat	Bigger segments (IZhO19_segments)	C++17	27 / 100	1 ms	856 KiB

segments

// https://codeforces.com/blog/entry/64479?#comment-484350
#include <iostream>
#include <cstdint>
#include <string>
#include <vector>

using namespace std;

#ifdef DEBUG 
#include "debuge.cpp"
#else
#define debug(...) 42
#endif

typedef            long long ll;
typedef       pair<int, int>  pii;
typedef         pair<ll, ll>  pll;
typedef pair<double, double> pdd;
typedef          vector<int>  vi;
typedef           vector<ll>  vll;
typedef          vector<pii>  vii;

#define                   fi  first
#define                   se  second
#define               all(v)  (v).begin(), (v).end()
#define                SZ(x)  ((int) (x).size())
#define                   pb  push_back
#define                   pf  push_front
#define                   lb  lower_bound
#define                   ub  upper_bound
 
#define         FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define         ROF(i, a, b) for (int i = (a); i > (b); --i)


void LPP(int &test)  {
	int n;
	cin >> n;
	vll a(n + 1), p(n + 1);
	vector<pll> dp(n + 1);      // number of segment - sum
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) p[i] = p[i - 1] + a[i];
	// subtask 4 
	dp[0].fi = dp[0].se = 0;
	for (int i = 1; i <= n; i++) {
		dp[i].fi = 0;
		dp[i].se = 5e15;
	}

	dp[0].fi = dp[0].se = 0;
	for (int i = 0; i < n; i++) {
		debug(i, dp[i]);
		if (p[n] - p[i] >= dp[i].se) {
			int lo = i, hi = n + 1;
			while (lo + 1 < hi) {
				int mi = (lo + hi) / 2;
				if (p[mi] - p[i] >= dp[i].se) {
					hi = mi;
				} else {
					lo = mi;
				}
			}
			pll tmp;
			tmp.fi = dp[i].fi + 1;
			tmp.se = p[hi] - p[i];
			if (tmp.fi > dp[hi].fi) {
				dp[hi].fi = tmp.fi;
				dp[hi].se = tmp.se;
			} else if (tmp.fi < dp[hi].fi) {
				
			} else {
				dp[hi].se = min(dp[hi].se, tmp.se);
			}
		}
		if (dp[i].fi > dp[i + 1].fi) {
			dp[i + 1].fi = dp[i].fi;
			dp[i + 1].se = dp[i].se + a[i + 1];
		} else if (dp[i].fi < dp[i + 1].fi) {
			if (dp[i].se <= a[i + 1] && a[i + 1] <= dp[i + 1].se) dp[i + 1].se = a[i + 1]; 
		} else {
			dp[i + 1].se = min(dp[i + 1].se, dp[i].se + a[i]);
		}
	}
	debug(dp[n]);
	cout << dp[n].fi;
}

int32_t main() {
	cin.tie(0) -> ios::sync_with_stdio(false);
	int tc = 1;
	// cin >> tc;
	for (int i = 1; i <= tc; i++) LPP(i);
}






































/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
*/

컴파일 시 표준 에러 (stderr) 메시지

segments.cpp: In function 'void LPP(int&)':
segments.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 42
      |                    ^~
segments.cpp:52:3: note: in expansion of macro 'debug'
   52 |   debug(i, dp[i]);
      |   ^~~~~
segments.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 42
      |                    ^~
segments.cpp:84:2: note: in expansion of macro 'debug'
   84 |  debug(dp[n]);
      |  ^~~~~

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