fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 2000010;
  6.  
  7. int a[N], to[N];
  8. long long s[N];
  9.  
  10. int main() {
  11.   int n, tt;
  12.   scanf("%d %d", &n, &tt);
  13.   for (int i = 0; i < n; i++) {
  14.     scanf("%d", a + i);
  15.   }
  16.   for (int i = 0; i < n; i++) {
  17.     a[n + i] = a[i];
  18.   }
  19.   s[0] = 0;
  20.   for (int i = 0; i < 2 * n; i++) {
  21.     s[i + 1] = s[i] + a[i];
  22.   }
  23.   for (int qq = 0; qq < tt; qq++) {
  24.     long long b;
  25.     cin >> b;
  26.     int j = 2 * n;
  27.     for (int i = 2 * n - 1; i >= 0; i--) {
  28.       while (s[j] - s[i] > b) {
  29.         j--;
  30.       }
  31.       to[i] = j;
  32.     }
  33.     int best = 0;
  34.     for (int i = 1; i < n; i++) {
  35.       if (to[i] - i < to[best] - best) {
  36.         best = i;
  37.       }
  38.     }
  39.     int ans = n;
  40.     int start = best;
  41.     for (int z = best; z <= to[best]; z++) {
  42.       int steps = 0;
  43.       int where = start;
  44.       while (where < start + n) {
  45.         steps++;
  46.         where = to[where];
  47.       }
  48.       if (steps < ans) {
  49.         ans = steps;
  50.       }
  51.       start++;
  52.       if (start >= n) {
  53.         start -= n;
  54.       }
  55.     }
  56.     printf("%d\n", ans);
  57.   }
  58.   return 0;
  59. }
Success #stdin #stdout 0s 34392KB
comments (?)
stdin
copy 
12 1
10 13 14 8 15 11 8 1 7 14 10 11
61
stdout
copy 
2
https://ideone.com/OKfcQJ
language:
C++ (gcc 8.3)
created:
9 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!