Submission #1135309

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135309		nuutsnoynton	도넛 (JOI14_ho_t3)	C++20	100 / 100	246 ms	1972 KiB

2014_ho_t3

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
	ll n, m, r, x, y, i, j, ans,s, lo, hi, mid, sum, t;

	cin >> n;
	
	ll a[n + 2], pre[n + 2];
	pre[0] = 0;
	ans = 0;
	for (i = 1; i <= n; i ++) cin >> a[i], pre[i] = pre[i - 1] + a[i];
	for (i = 1; i <= n; i ++) {
		lo = 1;
		hi = 1e18;
		while (lo < hi) {
			mid = (lo + hi)/2;
			 
			sum =pre[n];
			s = lower_bound(pre + 1, pre + n + 1, pre[i - 1] + mid) - pre;
			if ( s > n) {
				hi = mid;
				continue;
			}
			s ++;
		//	cout << s << "S";
			r = lower_bound(pre + 1, pre + n + 1, pre[s - 1] + mid) - pre;
			if ( r > n) {
				hi = mid;
				continue;
			}
			
			sum -= (pre[r ] - pre[i - 1]);
			//cout << mid << " " << sum << " " << r << endl;
			if( sum < mid) hi = mid;
			else lo = mid + 1;
		}
		ans = max(ans, lo);
	}
	cout << ans - 1 << endl;
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 30 / 30
• Subtask 4: 50 / 50