Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <iostream>
- #include <algorithm>
- #include <ctime>
- using namespace std;
- const int NMAX = 20;
- long long k, n, m;
- long long a[200100];
- long long t[200100];
- long long sum[200100];
- void read () {
- cin >> n >> m >> k;
- for (int i = 0; i < n; i++) {
- cin >> a[i];
- sum[i + 1] = sum[i] + a[i];
- }
- for (int i = 1; i <= m; i++) {
- cin >> t[i];
- }
- }
- void random_read () {
- srand (time(NULL));
- n = rand() % NMAX + 1;
- m = rand() % NMAX + 1;
- k = rand() % (NMAX * NMAX) + 1;
- for (int i = 0; i < n; i++) {
- a[i] = k = rand() % (NMAX * NMAX) + 1;
- sum[i + 1] = sum[i] + a[i];
- }
- for (int i = 1; i <= m; i++) {
- t[i] = rand() % (NMAX * NMAX) + 1;
- }
- sort (t, t + m + 1);
- }
- int solve1 () {
- long long sz = 0, prev = 0;
- for (int i = 1; i <= m; i++) {
- int add = t[i] - t[i - 1] - 1 - sz;
- sz += add;
- if (sz >= n) {
- int ans = n - prev + t[i - 1];
- if (ans > n) ans -= ans - n;
- cout << ans;
- return ans;
- }
- long long low = 0, high = sz, mid;
- while (low < high) {
- mid = low + (high - low) / 2;
- int val = sum[sz] - sum[sz - mid];
- if (val > k)
- high = mid;
- else low = mid + 1;
- }
- sz -= high;
- prev = sz;
- }
- cout << n - sz + t[m];
- return n - sz + t[m];
- }
- int solve2 () {
- long long sz = 0, prev = 0;
- for (int i = 1; i <= m; i++) {
- int add = t[i] - t[i - 1] - 1 - sz;
- sz += add;
- if (sz >= n) {
- int ans = n - prev + t[i - 1];
- if (ans > n) ans -= ans - n;
- cout << ans;
- return ans;
- }
- long long pos = -1;
- for (int i = 0; i <= sz; i++) {
- pos = i;
- int val = sum[sz] - sum [sz - i];
- if (val > k) break;
- }
- sz -= pos;
- prev = sz;
- }
- cout << n - sz + t[m];
- return n - sz + t[m];
- }
- int main () {
- read ();
- solve2 ();
- /*while (1) {
- random_read();
- if (solve1() != solve2()) {
- break;
- }
- }*/
- }
- /*
- 5 1 4
- 1
- 2
- 3
- 4
- 5
- 4
- 5 3 6
- 1
- 2
- 3
- 4
- 5
- 4 5 6
- */
Advertisement
Add Comment
Please, Sign In to add comment