Advertisement
Guest User

SecvMax

a guest
Feb 26th, 2020
106
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.12 KB | None | 0 0
  1. /// Solutie - Moca Andrei - O(n * logn)
  2. #include <bits/stdc++.h>
  3. #define ENTER ios::sync_with_stdio(false); fin.tie(0); fout.tie(0);
  4. #define EXIT fin.close(); fout.close(); return 0;
  5. using namespace std;
  6. ifstream fin("secvmaxval.in");
  7. ofstream fout("secvmaxval.out");
  8. int64_t val, x, minim = 1e9;
  9. vector<int64_t> sp;
  10. int n, lmax;
  11. inline bool Check(int l);
  12. int main()
  13. {
  14. ENTER
  15. fin >> n >> val;
  16. sp = vector<int64_t>(n + 1);
  17. for (int i = 1; i <= n; ++i)
  18. {
  19. fin >> x;
  20. sp[i] = sp[i - 1] + x;
  21. minim = min(minim, x);
  22. }
  23. if (val < minim) {
  24. fout << 0; EXIT
  25. }
  26. if (val >= sp[n]) {
  27. fout << n; EXIT
  28. }
  29. int st = 1, dr = n, mij;
  30. bool ok;
  31. while (st <= dr)
  32. {
  33. mij = (st + dr) / 2;
  34. ok = Check(mij);
  35. if (ok)
  36. {
  37. lmax = max(lmax, mij);
  38. st = mij + 1;
  39. }
  40. else dr = mij - 1;
  41. }
  42. fout << lmax;
  43. EXIT
  44. }
  45. bool Check(int l)
  46. {
  47. for (int i = 1; i <= n - l + 1; ++i)
  48. if (sp[i + l - 1] - sp[i - 1] <= val)
  49. return true;
  50. return false;
  51. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement