Iamtui1010

nkmaxseq

Nov 8th, 2021
93
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.20 KB | None | 0 0
  1. //#include<bits/stdc++.h>
  2. #include<iostream>
  3. #include<fstream>
  4. #include<vector>
  5.  
  6. #define long long long
  7. #define nln '\n'
  8.  
  9. const long N = 1e5+10;
  10.  
  11. using namespace std;
  12.  
  13. // Global variables: f1, f2, n, p, a, tol
  14.  
  15. fstream f1, f2;
  16.  
  17. inline void openf()
  18. {
  19.     f1.open("nkmaxseq.inp", ios:: in);
  20.     f2.open("nkmaxseq.out", ios:: out);
  21. }
  22.  
  23. inline void closef()
  24. {
  25.     f1.close();
  26.     f2.close();
  27. }
  28.  
  29. long p, n;
  30. vector<long> a;
  31. vector<long> tol;
  32.  
  33. void data()
  34. {
  35.     f1.tie(0)->sync_with_stdio(0);
  36.     f2.tie(0)->sync_with_stdio(0);
  37.     //cin.tie(0)->sync_with_stdio(0);
  38.     cin >> n >> p;
  39.     for (long i = 0; i != n; ++i)
  40.     {
  41.         long x;
  42.         cin >> x;
  43.         a.push_back(x);
  44.     }
  45.  
  46.     tol.resize(n, 0);
  47.     tol[0] = a[0];
  48.     for (long i = 1; i != n; ++i)
  49.         tol[i] = tol[i-1] + a[i];
  50. }
  51.  
  52. long sum(long i, long j)
  53. {
  54.     return (tol[j]-tol[i-1]);
  55. }
  56.  
  57. bool check(long len)
  58. {
  59.     for (long i = 0; i+len-1 != n; ++i)
  60.         if (sum(i, i+len-1) >= p)
  61.             return 1;
  62.     return 0;
  63. }
  64.  
  65. long ans = -1;
  66.  
  67. void process()
  68. {
  69.     for (long len = n; len >= 1; --len)
  70.         if (check(len))
  71.         {
  72.             ans = len;
  73.             return;
  74.         }
  75. }
  76.  
  77. void view()
  78. {
  79.     cout << ans << nln;
  80. }
  81.  
  82. int main()
  83. {
  84.     openf();
  85.     data();
  86.     process();
  87.     view();
  88.     closef();
  89.     return 0;
  90. }
Advertisement
Add Comment
Please, Sign In to add comment