Advertisement
a53

secvente4

a53
Nov 20th, 2020
114
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.17 KB | None | 0 0
  1. /* Secvente - O(N)
  2. * Florian Usurelu
  3. * scor: 100
  4. */
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7.  
  8. ifstream f ("secvente.in");
  9. ofstream g ("secvente.out");
  10.  
  11. const int nmax = 1e6 + 3;
  12. char s[nmax];
  13. int v[nmax], n, st[nmax], dr[nmax], k, sum, sol;
  14. int main()
  15. {
  16. f >> n >> k >> (s + 1);
  17.  
  18. for (int i = 1; i <= n; ++i)
  19. {
  20. v[i] = s[i] - '0';
  21. sum += v[i];
  22. }
  23.  
  24. if (sum < 2 * k)
  25. {
  26. g << -1;
  27. return 0;
  28. }
  29.  
  30. sum = 0;
  31.  
  32. for (int i = 1; i <= n; ++i)
  33. {
  34. sum += v[i];
  35. if(i - k >= 1)
  36. {
  37. sum -= v[i - k];
  38. st[i] = max(sum, st[i - 1]);
  39. }
  40.  
  41. if(i == k) st[i] = sum;
  42. }
  43.  
  44. sum = 0;
  45.  
  46. for (int i = n; i >= 0; --i)
  47. {
  48. sum += v[i];
  49. if(i + k <= n)
  50. {
  51. sum -= v[i + k];
  52. dr[i] = max(sum, dr[i + 1]);
  53. }
  54.  
  55. if(i == n - k + 1) dr[i] = sum;
  56. }
  57.  
  58. sol = 2e9;
  59.  
  60. for (int i = k; i + 1 <= n - k + 1; ++i)
  61. sol = min(sol, 2 * k - st[i] - dr[i + 1]);
  62.  
  63. g << sol;
  64.  
  65. return 0;
  66. }
  67.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement