Submission #51757

#	Time	Username	Problem	Language	Result	Execution time	Memory
51757		model_code	도넛 (JOI14_ho_t3)	C++17	100 / 100	166 ms	2304 KiB

2014_ho_t3

// O(N logN) solution
#include <cstdio>

int main()
{
  int n;
  scanf("%d",&n);
  static int A[1000000];
  long long AA=0;
  for(int i=0;i<n;i++){
    scanf("%d",A+i);
    AA+=A[i];
  }
  long long l=0,r=AA+1;
  while(l+1<r){
    long long m=(l+r)/2;
    static long long S[1000000];
    static int P[1000000];
    for(int i=0;i<n;i++){
      if(i>0){
	P[i]=P[i-1]-1;
	S[i]=S[i-1]-A[i-1];
      }
      else{
	P[i]=0;
	S[i]=0;
      }
      while(S[i]<m){
	S[i]+=A[(i+P[i])%n];
	P[i]++;
      }
    }
    bool B=0;
    for(int i=0;i<n;i++){
      if(AA-S[i]-S[(i+P[i])%n]>=m){
	B=1;
      }
    }
    if(B){
      l=m;
    }
    else{
      r=m;
    }
  }
  printf("%lld\n",l);
  return 0;
}

Compilation message (stderr)

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

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