Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <string>
- #include <math.h>
- #include <climits>
- //#pragma GCC optimize("O3, unroll-loops");
- #include <list>
- #include <map>
- #include <set>
- #include <queue>
- #include <unordered_map>
- #include <unordered_set>
- //#include <chrono>
- //#include <fstream>
- //#include <bits/stdc++.h>
- #define mp make_pair
- #define pb push_back
- #define eb emplace_back
- #define x first
- #define y second
- #define sz(x) (int)x.size()
- #define all(x) begin(x), end(x)
- #define rall(x) rbegin(x), rend(x)
- #define FOR(i,a,b) for (int i = (a); i < (b); i++)
- #define RFOR(i,b,a) for (int i = (b) - 1; i >= (a); i--)
- using namespace std;
- typedef unsigned long long ull;
- typedef long long ll;
- typedef long double ld;
- typedef pair<int, int> pi;
- typedef pair<ll, ll> pl;
- typedef vector<int> veci;
- typedef vector<bool> vecb;
- typedef vector<vector<int>> vvi;
- typedef vector<vector<bool>> vvb;
- const int INF_I = 1e9;
- const ll INF_LL = 1e18;
- int main() {
- /*ifstream cin("in.txt");
- ofstream cout("out.txt");
- auto start_time = chrono::high_resolution_clock::now();*/
- ios::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- int n, k;
- cin >> n >> k;
- veci a(n);
- for (int i = 0; i < n; i++)
- cin >> a[i];
- vector<ull> sum(n);
- sum[0] = a[0];
- for (int i = 1; i < n; i++)
- sum[i] = sum[i - 1] + a[i];
- vector<ull> p(n);
- for (int i = k-1; i < n; i++)
- p[i] = max(p[i - 1], sum[i] - (i >= k ? sum[i - k] : 0));
- vector<ull> s(n);
- for (int i = n - k; i >= 0; i--)
- s[i] = max(s[i + 1], sum[i + k - 1] - (i > 0 ? sum[i - 1] : 0));
- ull minn = ULLONG_MAX;
- for (int i = 0; i < n; i++)
- minn = min(minn, max((i > 0 ? p[i - 1] : 0), (i + k < n ? s[i + k] : 0)));
- cout << minn << "\n";
- /*auto end_time = chrono::high_resolution_clock::now();
- chrono::duration<double> duration = end_time - start_time;
- cout << duration.count() << "\n";
- cin.close();
- cout.close();*/
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement