fork download
  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
stdin
100000
1
100
1
100
stdout
10000100