prestige

Untitled

Mar 17th, 2014
218
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.03 KB | None | 0 0
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <ctime>
  5. using namespace std;
  6.  
  7. const int NMAX = 20;
  8. long long k, n, m;
  9. long long a[200100];
  10. long long t[200100];
  11. long long sum[200100];
  12. void read () {
  13. cin >> n >> m >> k;
  14. for (int i = 0; i < n; i++) {
  15. cin >> a[i];
  16. sum[i + 1] = sum[i] + a[i];
  17. }
  18. for (int i = 1; i <= m; i++) {
  19. cin >> t[i];
  20. }
  21. }
  22. void random_read () {
  23. srand (time(NULL));
  24. n = rand() % NMAX + 1;
  25. m = rand() % NMAX + 1;
  26. k = rand() % (NMAX * NMAX) + 1;
  27. for (int i = 0; i < n; i++) {
  28. a[i] = k = rand() % (NMAX * NMAX) + 1;
  29. sum[i + 1] = sum[i] + a[i];
  30. }
  31. for (int i = 1; i <= m; i++) {
  32. t[i] = rand() % (NMAX * NMAX) + 1;
  33. }
  34. sort (t, t + m + 1);
  35. }
  36. int solve1 () {
  37. long long sz = 0, prev = 0;
  38. for (int i = 1; i <= m; i++) {
  39. int add = t[i] - t[i - 1] - 1 - sz;
  40. sz += add;
  41. if (sz >= n) {
  42. int ans = n - prev + t[i - 1];
  43. if (ans > n) ans -= ans - n;
  44. cout << ans;
  45. return ans;
  46. }
  47. long long low = 0, high = sz, mid;
  48. while (low < high) {
  49. mid = low + (high - low) / 2;
  50. int val = sum[sz] - sum[sz - mid];
  51. if (val > k)
  52. high = mid;
  53. else low = mid + 1;
  54. }
  55. sz -= high;
  56. prev = sz;
  57. }
  58. cout << n - sz + t[m];
  59. return n - sz + t[m];
  60. }
  61. int solve2 () {
  62. long long sz = 0, prev = 0;
  63. for (int i = 1; i <= m; i++) {
  64. int add = t[i] - t[i - 1] - 1 - sz;
  65. sz += add;
  66. if (sz >= n) {
  67. int ans = n - prev + t[i - 1];
  68. if (ans > n) ans -= ans - n;
  69. cout << ans;
  70. return ans;
  71. }
  72. long long pos = -1;
  73. for (int i = 0; i <= sz; i++) {
  74. pos = i;
  75. int val = sum[sz] - sum [sz - i];
  76. if (val > k) break;
  77. }
  78. sz -= pos;
  79. prev = sz;
  80. }
  81. cout << n - sz + t[m];
  82. return n - sz + t[m];
  83. }
  84. int main () {
  85. read ();
  86. solve2 ();
  87. /*while (1) {
  88. random_read();
  89. if (solve1() != solve2()) {
  90. break;
  91. }
  92. }*/
  93. }
  94. /*
  95. 5 1 4
  96. 1
  97. 2
  98. 3
  99. 4
  100. 5
  101. 4
  102.  
  103. 5 3 6
  104. 1
  105. 2
  106. 3
  107. 4
  108. 5
  109. 4 5 6
  110. */
Advertisement
Add Comment
Please, Sign In to add comment