fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MaxN=3e5;
  5. const int MaxA=1e7;
  6.  
  7. int num[MaxN+1];
  8. int pos[MaxN+1];
  9. long prS[MaxN+1];
  10.  
  11. bool comp(int lhs,int rhs){
  12. 	return num[lhs]<num[rhs]; }
  13.  
  14. int main(){
  15. 	int N;
  16.  
  17. 	cin>>N;
  18. 	for(int n=1; n<=N; n+=1)
  19. 		cin>>num[n];
  20.  
  21. 	prS[0]=0;
  22. 	for(int n=1; n<=N; n+=1)
  23. 		prS[n]=prS[n-1]+num[n];
  24. 	iota(pos+1, pos+1+N, 1);
  25. 	sort(pos+1, pos+1+N,comp);
  26.  
  27. 	int L=1, R=N;
  28. 	for(int n=1; n<=N; n+=1){
  29. 		int p=pos[n];
  30. 		if( (L<=p && p<=R)==0 )
  31. 			continue;
  32. 		long sumL=prS[p-1]-prS[L-1];
  33. 		long sumR=prS[ R ]-prS[ p ];
  34. 		(sumL<=sumR)? L=p+1: R=p-1;
  35. 		if( L==R )
  36. 			break;
  37. 	}
  38. 	cout<<num[L];
  39. }
Success #stdin #stdout 0.01s 7672KB
comments (?)
stdin
copy 
5
4 2 3 1 5
stdout
copy 
4
https://ideone.com/jO6tmw
language:
C++ (gcc 8.3)
created:
13 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!