제출 #1287368

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1287368		kerem	도넛 (JOI14_ho_t3)	C++20	100 / 100	28 ms	2136 KiB

2014_ho_t3

#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define pb push_back
#define emb emplace_back
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define sp << " " <<
#define N 100000
#define inf (int)1e14
typedef pair<int,int> ii;
typedef tuple<int,int,int> iii;

int n,sum=0,a[2*N];
bool calc(int x){
	int i1=0,i2=0,i3=0;
	int sum1=0,sum2=0;
	while(i1<n){
		while(i2<i1+n && sum1<x){
			sum1+=a[i2];
			sum2-=a[i2];
			i2++;
		}
		while(i3<i1+n && sum2<x){
			sum2+=a[i3];
			i3++;
		}
		if(sum1>=x && sum2>=x && sum-sum1-sum2>=x)
			return true;
		sum1-=a[i1];
		i1++;
	}
	return false;
}
void solve(){
	cin >> n;
	for(int i=0;i<n;i++){
		cin >> a[i];
		a[n+i]=a[i];
		sum+=a[i];
	}
	int l=1,r=sum/3;
	while(l<r){
		int mid=(l+r+1)/2;
		if(calc(mid)) l=mid;
		else r=mid-1;
	}
	cout << l << endl;
}
int32_t main(){
	//~ freopen("hopscotch.in","r",stdin);
	//~ freopen("hopscotch.out","w",stdout);
	
	cout << fixed << setprecision(0);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	
	int test=1;
	//~ cin >> test;
	while(test--) solve();
}

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