ProgMe

Untitled

Apr 18th, 2020
146
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.95 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define int int64_t
  3.  
  4. using namespace std;
  5. deque <int> a, b, c;
  6.  
  7. int get(int l, int r){
  8. if(r < l) return 0LL;
  9. if(l == 0) return c[r];
  10. else return c[r] - c[l - 1];
  11. }
  12.  
  13.  
  14. int32_t main()
  15. {
  16. int t;
  17. cin >> t;
  18. while (t--)
  19. {
  20. int n;
  21. cin >> n;
  22. a.resize(n);
  23. b.resize(n);
  24. c.resize(n);
  25. for (int i = 0; i < n; i++)
  26. cin >> a [i] >> b [i];
  27. for (int i = 0; i < n; i++)
  28. {
  29. if (i == n - 1)
  30. c [0] = max(a [0] - b [i], 0LL);
  31. else
  32. c [i + 1] = max(a [i + 1] - b [i], 0LL);
  33. }
  34. for (int i = 1; i < n; i++)
  35. c [i] += c [i - 1];
  36. int ans = LLONG_MAX;
  37. for (int i = 0; i < n; i++)
  38. {
  39. int cnt = a [i] + get(0, i - 1) + get(i + 1, n - 1);
  40. ans = min(ans, cnt);
  41. }
  42. cout << ans << "\n";
  43. }
  44. }
Advertisement
Add Comment
Please, Sign In to add comment