trafik

Untitled

Oct 10th, 2022
848
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.66 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define ull unsigned long long
  4. #define ld long double
  5. #define len(v) (int)v.size()
  6. #define all(v) v.begin(), v.end()
  7. #define rall(v) v.rbegin(), v.rend()
  8. #define pii pair<int, int>
  9. #define vi vector<int>
  10. #define vii vector<vector<int>>
  11. #define vpii vector<pair<int, int>>
  12. #define ull unsigned long long
  13. //#define int long long
  14. //#define ll ull
  15. const int N = 1e6 + 1;
  16. const int maxn = 5e6 + 10;
  17. const int C = 20;
  18. const int logn = 20;
  19. const ll inf = 1e15;
  20. const ll mod = 1e9 + 7;
  21. const int M = 1e9;
  22. const ull M2 = 998244353;
  23. const ld eps = 1e-6;
  24. using namespace std;
  25.  
  26. template<class T>
  27. istream &operator>>(istream &in, vector<T> &a) {
  28.     for (auto &i : a)
  29.         in >> i;
  30.     return in;
  31. }
  32.  
  33. template<class T>
  34. ostream &operator<<(ostream &out, vector<T> &a) {
  35.     for (auto &i : a)
  36.         out << i << ' ';
  37.     return out;
  38. }
  39. void solve() {
  40.     ll n, k; cin >> n >> k;
  41.     vector<ll> a(n), b(n - k + 1, 0ull);
  42.     cin >> a;
  43.     ll su = 0;
  44.     for (int i = 0; i < k; ++i)
  45.         su += a[i];
  46.     b[0] = su;
  47.     for (int i = 1; i < n - k + 1; ++i) {
  48.         b[i] = b[i - 1] + a[i + k - 1] - a[i - 1];
  49.     }
  50.     vector<ll> p(n - k + 1), s(n - k + 1);
  51.     for (int i = k; i < n - k + 1; ++i)
  52.         p[i] = max(p[i - 1], b[i - k]);
  53.     for (int i = n - 2 * k; i >= 0; --i)
  54.         s[i] = max(s[i + 1], b[i + k]);
  55.     ll ans = inf;
  56.     for (int i = 0; i < n - k + 1; ++i)
  57.         ans = min(ans, max(p[i], s[i]));
  58.     cout << ans;
  59.  
  60. }
  61.  
  62. signed main() {
  63.     ios::sync_with_stdio(false);
  64.     cin.tie(nullptr);
  65.     cout.tie(nullptr);
  66.  
  67.     int T = 1;
  68.     //cin >> T;
  69.     while (T--)
  70.         solve();
  71. }
Advertisement
Add Comment
Please, Sign In to add comment