fork download
copy 
  1. /*
  2. Task: 1443C
  3. Date: Dec 20, 2020
  4. Author: aLittleLove (Minh Vu)
  5. */
  6.  
  7. #include<bits/stdc++.h>
  8. #define rep(i,n) for (int i=0, _n=n; i<_n; i++)
  9. #define FOR(i,a,b) for (int _a=(a), _b=(b), i=_a; _a<=_b?i<=_b:i>=_b; _a<=_b?i++:i--)
  10. #define _mem(a, b) memset(a, (b), sizeof(a))
  11. #define pb push_back
  12. #define fi first
  13. #define se second
  14. #define sz(a) int((a).size())
  15.  
  16. using namespace std;
  17. typedef long long ll;
  18. typedef int64_t i64;
  19. typedef pair<int, int> pii;
  20. typedef vector<pii> vii;
  21. typedef vector<int> vi;
  22. const int N = 2e5 + 5;
  23. const int inf = 1e9;
  24. const int mod = 1e9 + 7;
  25. const double pi = atan(1) * 4.0;
  26. template<typename T, typename U> inline void mini(T &x, U y) { if(y < x) x = y; }
  27. template<typename T, typename U> inline void maxi(T &x, U y) { if(x < y) x = y; }
  28.  
  29. int n; 
  30. pair<i64, i64> a[N];
  31.  
  32. bool check(i64 x)
  33. {
  34.     i64 res = 0, cur = 0;
  35.     FOR(i,1,n)
  36.     {
  37.         if (a[i].fi <= x)
  38.         {
  39.             res = max(res, a[i].fi);
  40.         }
  41.         else 
  42.         {
  43.             res = max(res, cur + a[i].se);
  44.             cur += a[i].se;
  45.         }
  46.     }
  47.     return res<=x;
  48. }
  49.  
  50. void Solve()
  51. {
  52.     cin >> n;
  53.     FOR(i,1,n) cin >> a[i].fi;
  54.     FOR(i,1,n) cin >> a[i].se;
  55.     i64 l = 0, r = 1e18;
  56.     i64 ans = 1e18;
  57.     while (l<=r)
  58.     {
  59.         i64 mid = (l + r)/2ll;
  60.         if (check(mid)) 
  61.         {
  62.             r = mid - 1;
  63.             ans = mid;
  64.         }
  65.         else l = mid + 1;
  66.     }
  67.     cout << ans << '\n';
  68. }
  69.  
  70. int main()
  71. {
  72.     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  73.     //freopen("input.txt","r",stdin);
  74.     int nTest; cin >> nTest;
  75.     while (nTest--) Solve();
  76.  
  77.     return 0;
  78. }
Success #stdin #stdout 0s 5020KB
comments (?)
stdin
copy 
4
4
3 7 4 5
2 1 2 4
4
1 2 3 4
3 3 3 3
2
1 2
10 10
2
10 10
1 2
stdout
copy 
5
3
2
3
https://ideone.com/5TjG7s
Codeforces 1443C
language:
C++14 (gcc 8.3)
created:
4 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!