Advertisement
Raslboyy

112745

Jan 22nd, 2020
119
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.96 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <string>
  5. #include <math.h>
  6. #include <climits>
  7.  
  8. //#pragma GCC optimize("O3, unroll-loops");
  9.  
  10. #include <list>
  11. #include <map>
  12. #include <set>
  13. #include <queue>
  14. #include <unordered_map>
  15. #include <unordered_set>
  16.  
  17. //#include <chrono>
  18. //#include <fstream>
  19. //#include <bits/stdc++.h>
  20.  
  21. #define mp make_pair
  22. #define pb push_back
  23. #define eb emplace_back
  24. #define x first
  25. #define y second
  26. #define sz(x) (int)x.size()
  27. #define all(x) begin(x), end(x)
  28. #define rall(x) rbegin(x), rend(x)
  29. #define FOR(i,a,b) for (int i = (a); i < (b); i++)
  30. #define RFOR(i,b,a) for (int i = (b) - 1; i >= (a); i--)
  31.  
  32. using namespace std;
  33.  
  34. typedef unsigned long long ull;
  35. typedef long long ll;
  36. typedef long double ld;
  37. typedef pair<int, int> pi;
  38. typedef pair<ll, ll> pl;
  39. typedef vector<int> veci;
  40. typedef vector<bool> vecb;
  41. typedef vector<vector<int>> vvi;
  42. typedef vector<vector<bool>> vvb;
  43.  
  44. const int INF_I = 1e9;
  45. const ll INF_LL = 1e18;
  46.  
  47. int main() {
  48.     /*ifstream cin("in.txt");
  49.     ofstream cout("out.txt");
  50.     auto start_time = chrono::high_resolution_clock::now();*/
  51.  
  52.     ios::sync_with_stdio(false);
  53.     cin.tie(0);
  54.     cout.tie(0);
  55.  
  56.    
  57.     int n, k;
  58.     cin >> n >> k;
  59.     veci a(n);
  60.     for (int i = 0; i < n; i++)
  61.         cin >> a[i];
  62.  
  63.     vector<ull> sum(n);
  64.     sum[0] = a[0];
  65.     for (int i = 1; i < n; i++)
  66.         sum[i] = sum[i - 1] + a[i];
  67.  
  68.     vector<ull> p(n);
  69.     for (int i = k-1; i < n; i++)
  70.         p[i] = max(p[i - 1], sum[i] - (i >= k ? sum[i - k] : 0));
  71.  
  72.     vector<ull> s(n);
  73.     for (int i = n - k; i >= 0; i--)
  74.         s[i] = max(s[i + 1], sum[i + k - 1] - (i > 0 ? sum[i - 1] : 0));
  75.  
  76.     ull minn = ULLONG_MAX;
  77.     for (int i = 0; i < n; i++)
  78.         minn = min(minn, max((i > 0 ? p[i - 1] : 0), (i + k < n ? s[i + k] : 0)));
  79.  
  80.     cout << minn << "\n";
  81.  
  82.     /*auto end_time = chrono::high_resolution_clock::now();
  83.     chrono::duration<double> duration = end_time - start_time;
  84.     cout << duration.count() << "\n";
  85.     cin.close();
  86.     cout.close();*/
  87.     return 0;
  88. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement