fork(4) download
copy 
  1. #include <bits/stdc++.h>
  2. #define FN(i, n) for (int i = 0; i < (int)(n); ++i)
  3. #define FEN(i,n) for (int i = 1;i <= (int)(n); ++i)
  4. #define FA(i, a) for (__typeof((a).begin()) i = (a).begin(); i != (a).end(); i++)
  5. #define pb push_back
  6. #define mp make_pair
  7. #define sz(a) (int)(a).size()
  8. #define f first
  9. #define s second
  10. #define pii pair<int,int>
  11. #define vi vector<int>
  12. #define ll long long
  13. #define db long double
  14. using namespace std ;
  15. const int L =2e5+5 ;
  16. ll T[L],ST[L] ; ll A[2005],ans[2005] ;
  17. int N ;
  18. set< pair<ll,int> > X ;
  19. // struct comp{bool operator()(int x,int y){return A[x]<A[y];}};
  20. void bs(ll l,ll r,vi &todo)
  21. {
  22. 	// cout<<"l = "<<l<<" r= "<<r<<" with elements "<<sz(todo)<<endl ;
  23. 	if(l==r)
  24. 	{
  25. 		FN(i,sz(todo)) ans[todo[i]]=l ;
  26. 		todo.clear() ;
  27. 		return ;
  28. 	}
  29. 	ll m = (l+r)/2 ;
  30. 	ll tot = 0 ;
  31. 	FEN(i,N) tot += max(m-ST[i],(ll)0)/T[i] ;
  32. 	vi Left,Right ;
  33. 	FN(i,sz(todo))
  34. 	{
  35. 		if(A[todo[i]]<=tot) Left.pb(todo[i]) ;
  36. 		else Right.pb(todo[i]) ;
  37. 	}
  38. 	todo.clear() ;
  39. 	if(sz(Left)>0) bs(l,m,Left) ;
  40. 	if(sz(Right)>0) bs(m+1,r,Right) ;
  41. }
  42. int main()
  43. {
  44. 	std::ios::sync_with_stdio(false);
  45. 	int M ; cin>>N>>M ;
  46. 	FEN(i,N) cin>>T[i] ;
  47. 	sort(T+1,T+N+1) ;
  48. 	ST[1]=0 ; X.insert(mp(T[1],1)) ;
  49. 	for(int i=2;i<=N;++i)
  50. 	{
  51. 		ST[i] = X.begin()->f ;
  52. 		int x = X.begin()->s ;
  53. 		X.erase(X.begin()) ;
  54. 		X.insert(mp(ST[i]+T[x],x)) ;
  55. 		X.insert(mp(ST[i]+T[i],i)) ;
  56. 	}
  57. 	X.clear() ;
  58. 	FEN(i,M) cin>>A[i] ;
  59. 	vi todo ; FEN(i,M) todo.pb(i) ;
  60. 	// sort(todo.begin(),todo.end(),comp) ;
  61. 	bs(1,(ll)1e13+5,todo) ;
  62. 	FEN(i,M) cout<<ans[i]<<endl ;
  63. 	return 0 ;
  64. }
  65.  
Runtime error #stdin #stdout #stderr 1.92s 531968KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/dXcbpq
language:
C++ (gcc 8.3)
created:
8 years 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!