Submission #95323

#	Time	Username	Problem	Language	Result	Execution time	Memory
95323		Retro3014	도넛 (JOI14_ho_t3)	C++17	100 / 100	465 ms	3064 KiB

2014_ho_t3

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <deque>

using namespace std;
typedef long long ll;
#define MAX_N 100000

int N;
deque<ll> dq;
ll sum[MAX_N+1], ans;

ll calc(int x, int y){
	if(x<=y){
		if(x==0)	return sum[y];
		else 	return sum[y]-sum[x-1];
	}else{
		return sum[y]+sum[N-1]-sum[x-1];
	}
}

ll calc2(int x, int y){
	ll ret = 0;
	int s = 0, e = y, m;
	while(s<e){
		m = (s+e)/2;
		ll s1 = calc(x, (x+m)%N), s2 = calc((x+m+1)%N, (x+y)%N);
		ret = max(ret, min(s1, s2));
		if(s1<=s2)	s = m+1;
		else	e = m;
	}
	return ret;
}


int main(){
	scanf("%d", &N);
	for(int i=0; i<N; i++){
		ll x;
		scanf("%lld", &x);
		dq.push_back(x);
	}
	for(int i=0; i<dq.size(); i++){
		if(i==0)	sum[i] = dq[i];
		else	sum[i] = sum[i-1]+dq[i];
	}
	for(int st=0; st<N; st++){
		if(calc2((st+1)%N, N-2)<calc(st, st))	continue;
		int s = 0, e = N-1, m;
		while(s<e){
			m = (s+e)/2+1;
			if(calc2((st+m+1)%N, N-1-(m+1)%N)>=calc(st, (st+m)%N)){
				s = m;
			}else{
				e = m-1;
			}
		}
		//cout<<st<<" "<<s<<endl;
		ans = max(ans, calc(st, (st+s)%N));
	}
	printf("%lld", ans);
	return 0;
}

Compilation message (stderr)

2014_ho_t3.cpp: In function 'int main()':
2014_ho_t3.cpp:45:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<dq.size(); i++){
               ~^~~~~~~~~~
2014_ho_t3.cpp:39: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:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &x);
   ~~~~~^~~~~~~~~~~~

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