Submission #151419

#	Time	Username	Problem	Language	Result	Execution time	Memory
151419		TadijaSebez	도넛 (JOI14_ho_t3)	C++11	100 / 100	270 ms	3804 KiB

2014_ho_t3

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=200050;
int a[N];
ll sum[N];
int main()
{
	int n;
	scanf("%i",&n);
	for(int i=1;i<=n;i++) scanf("%i",&a[i]),a[i+n]=a[i];
	for(int i=1;i<=2*n;i++) sum[i]=sum[i-1]+a[i];
	ll all=sum[n],ans=0;
	function<ll(int,ll)> GetR=[&](int i, ll need)
	{
		int top=i+n-1,bot=i,mid,ans;
		while(top>=bot)
		{
			mid=top+bot>>1;
			if(sum[mid]-sum[i-1]>=need) ans=mid,top=mid-1;
			else bot=mid+1;
		}
		return sum[ans]-sum[i-1];
	};
	function<ll(int,ll)> GetL=[&](int i, ll need)
	{
		int top=i,bot=i-n+1,mid,ans;
		while(top>=bot)
		{
			mid=top+bot>>1;
			if(sum[i]-sum[mid-1]>=need) ans=mid,bot=mid+1;
			else top=mid-1;
		}
		return sum[i]-sum[ans-1];
	};
	for(int i=1,j=n;i<=n;i++)
	{
		ll top=all/3,bot=ans+1,mid;
		while(top>=bot)
		{
			mid=top+bot>>1;
			if(all-GetR(i,mid)-GetL(j,mid)>=mid) ans=mid,bot=mid+1;
			else top=mid-1;
		}
		j=i+n;
	}
	printf("%lld\n",ans);
	return 0;
}

Compilation message (stderr)

2014_ho_t3.cpp: In lambda function:
2014_ho_t3.cpp:19:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    mid=top+bot>>1;
        ~~~^~~~
2014_ho_t3.cpp: In lambda function:
2014_ho_t3.cpp:30:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    mid=top+bot>>1;
        ~~~^~~~
2014_ho_t3.cpp: In function 'int main()':
2014_ho_t3.cpp:41:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    mid=top+bot>>1;
        ~~~^~~~
2014_ho_t3.cpp:10:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
2014_ho_t3.cpp:11:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%i",&a[i]),a[i+n]=a[i];
                        ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
2014_ho_t3.cpp: In static member function 'static _Res std::_Function_handler<_Res(_ArgTypes ...), _Functor>::_M_invoke(const std::_Any_data&, _ArgTypes&& ...) [with _Res = long long int; _Functor = main()::<lambda(int, long long int)>; _ArgTypes = {int, long long int}]':
2014_ho_t3.cpp:23:17: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   return sum[ans]-sum[i-1];
          ~~~~~~~^
2014_ho_t3.cpp:16:27: note: 'ans' was declared here
   int top=i+n-1,bot=i,mid,ans;
                           ^~~
2014_ho_t3.cpp: In static member function 'static _Res std::_Function_handler<_Res(_ArgTypes ...), _Functor>::_M_invoke(const std::_Any_data&, _ArgTypes&& ...) [with _Res = long long int; _Functor = main()::<lambda(int, long long int)>; _ArgTypes = {int, long long int}]':
2014_ho_t3.cpp:34:24: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   return sum[i]-sum[ans-1];
                     ~~~^~
2014_ho_t3.cpp:27:27: note: 'ans' was declared here
   int top=i,bot=i-n+1,mid,ans;
                           ^~~

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