Submission #153828

#	Time	Username	Problem	Language	Result	Execution time	Memory
153828		songc	도넛 (JOI14_ho_t3)	C++14	100 / 100	399 ms	2936 KiB

2014_ho_t3

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

int N;
LL ans, S[101010], RS[101010];

bool chk(LL k){
	for (int i=1; i<N; i++){
		int l = N+1-(lower_bound(RS+N-i+1, RS+N+1, k+RS[N-i])-RS);
		int r = lower_bound(S+i+1, S+N+1, k+S[i])-S;
		if (l < 1 || N < r) continue;
		if (S[l-1] + S[N] - S[r] >= k) return true;
	}
	return false;
}

int main(){
	scanf("%d", &N);
	for (int i=1; i<=N; i++){
		scanf("%lld", &S[i]);
		RS[N-i+1] = S[i];
	}
	for (int i=1; i<=N; i++) S[i] += S[i-1], RS[i] += RS[i-1];
	LL L=0, R=(1ll<<60);
	while (L<=R){
		LL mid = (L+R)/2;
		if (chk(mid)) ans=mid, L=mid+1;
		else R = mid-1;
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

2014_ho_t3.cpp: In function 'int main()':
2014_ho_t3.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
2014_ho_t3.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &S[i]);
   ~~~~~^~~~~~~~~~~~~~~

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