prestige

Untitled

Mar 14th, 2014
173
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.83 KB | None | 0 0
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. long long k, n, m;
  7. long long a[200100];
  8. long long t[200100];
  9. long long sum[200100];
  10. int main () {
  11. cin >> n >> m >> k;
  12. for (int i = 0; i < n; i++) {
  13. cin >> a[i];
  14. sum[i + 1] = sum[i] + a[i];
  15. }
  16. long long sz = 0, prev = 0;
  17. for (int i = 1; i <= m; i++) {
  18. cin >> t[i];
  19. sz += t[i] - t[i - 1] - 1 - sz;
  20. if (sz >= n) {
  21. cout << n - prev + t[i - 1];
  22. return 0;
  23. }
  24. long long low = 0, high = sz, mid;
  25. while (low < high) {
  26. mid = low + (high - low) / 2;
  27. int val = sum[sz] - sum[sz - mid];
  28. if (val > k)
  29. high = mid;
  30. else low = mid + 1;
  31. }
  32. sz -= high;
  33. prev = sz;
  34. }
  35. cout << n - sz + t[m];
  36. }
  37. /*
  38. 5 1 4
  39. 1
  40. 2
  41. 3
  42. 4
  43. 5
  44. 4
  45.  
  46. 5 3 6
  47. 1
  48. 2
  49. 3
  50. 4
  51. 5
  52. 4 5 6
  53. */
Advertisement
Add Comment
Please, Sign In to add comment