Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define ll long long
- #define ull unsigned long long
- #define ld long double
- #define len(v) (int)v.size()
- #define all(v) v.begin(), v.end()
- #define rall(v) v.rbegin(), v.rend()
- #define pii pair<int, int>
- #define vi vector<int>
- #define vii vector<vector<int>>
- #define vpii vector<pair<int, int>>
- #define ull unsigned long long
- //#define int long long
- //#define ll ull
- const int N = 1e6 + 1;
- const int maxn = 5e6 + 10;
- const int C = 20;
- const int logn = 20;
- const ll inf = 1e15;
- const ll mod = 1e9 + 7;
- const int M = 1e9;
- const ull M2 = 998244353;
- const ld eps = 1e-6;
- using namespace std;
- template<class T>
- istream &operator>>(istream &in, vector<T> &a) {
- for (auto &i : a)
- in >> i;
- return in;
- }
- template<class T>
- ostream &operator<<(ostream &out, vector<T> &a) {
- for (auto &i : a)
- out << i << ' ';
- return out;
- }
- void solve() {
- ll n, k; cin >> n >> k;
- vector<ll> a(n), b(n - k + 1, 0ull);
- cin >> a;
- ll su = 0;
- for (int i = 0; i < k; ++i)
- su += a[i];
- b[0] = su;
- for (int i = 1; i < n - k + 1; ++i) {
- b[i] = b[i - 1] + a[i + k - 1] - a[i - 1];
- }
- vector<ll> p(n - k + 1), s(n - k + 1);
- for (int i = k; i < n - k + 1; ++i)
- p[i] = max(p[i - 1], b[i - k]);
- for (int i = n - 2 * k; i >= 0; --i)
- s[i] = max(s[i + 1], b[i + k]);
- ll ans = inf;
- for (int i = 0; i < n - k + 1; ++i)
- ans = min(ans, max(p[i], s[i]));
- cout << ans;
- }
- signed main() {
- ios::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- int T = 1;
- //cin >> T;
- while (T--)
- solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment