fork(1) download
copy 
  1. #include <iostream>
  2. #include <set>
  3. #include <climits>
  4. using namespace std;
  5.  
  6.  
  7. int inf = INT_MAX;
  8.  
  9. int main() {
  10. 	cin.sync_with_stdio(false);
  11. 	int n;
  12. 	cin >> n;
  13. 	int na;
  14. 	cin >> na;
  15. 	multiset<pair<int, int> > s;
  16. 	int a[na];
  17. 	int resa[n];
  18. 	for(int i=0; i<na; i++)
  19. 	{
  20. 		cin >> a[i];
  21. 		s.insert({a[i], a[i]});
  22. 	}
  23. 	for(int i=0; i<n; i++)
  24. 	{
  25. 		auto it=s.begin();
  26. 		int val=it->first;
  27. 		int t=it->second;
  28. 		s.erase(it);
  29. 		s.insert({val+t, t});
  30. 		resa[i]=val;
  31. 	}
  32. 	int nb;
  33. 	cin >> nb;
  34. 	int b[nb];
  35. 	for(int i=0; i<nb; i++)
  36. 	{
  37. 		cin >> b[i];
  38. 	}
  39. 	multiset<pair<int, int> > q;
  40. 	long long l=resa[n-1], r=10000100;
  41. 	while(l<r)
  42. 	{
  43. 		int w=0;
  44. 		int m=(l+r)/2;
  45. 		for(int i=0; i<nb; i++)
  46. 		{
  47. 			q.insert({b[i], b[i]});
  48. 		}
  49. 		q.insert({inf, inf});
  50. 		for(int i=n-1; i>=0; i--)
  51. 		{
  52. 			int y=m-resa[i];
  53. 			auto x=q.begin();
  54. 			if(y<(x->first))
  55. 			{
  56. 				w++;
  57. 				break;
  58. 			}
  59. 			else{
  60. 				auto it=q.lower_bound({y, -1});
  61. 				int z=it->first;
  62. 				if(z>y)
  63. 					it--;
  64. 				int val=it->first;
  65. 				int t=it->second;
  66. 				q.erase(it);
  67. 				q.insert({val+t, t});
  68. 			}
  69.  
  70. 		}
  71. 		if(w==0)
  72. 			r=m;
  73. 		else
  74. 			l=m+1;
  75. 		q.clear();	
  76. 	}
  77. 	cout << l << endl;
  78. 	return 0;
  79. }
Success #stdin #stdout 0.01s 4488KB
comments (?)
stdin
copy 
100000
1
100
1
100
stdout
copy 
10000100
https://ideone.com/6K67X7
language:
C++14 (gcc 8.3)
created:
6 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!