max_subarray_sum_ii.cpp (810B)
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 using ui = unsigned int; 6 using l = long; 7 using ul = unsigned long; 8 using ll = long long; 9 using ull = unsigned long long; 10 11 using vi = vector<int>; 12 using vui = vector<ui>; 13 using vl = vector<l>; 14 using vul = vector<ul>; 15 using vll = vector<ll>; 16 using vull = vector<ull>; 17 18 void solve() 19 { 20 int n, a, b; 21 cin >> n >> a >> b; 22 long long x[n]; 23 long long pre[n+1] = { 0 }; 24 for (int i = 0; i < n; i++) { 25 cin >> x[i]; 26 pre[i+1] = x[i] + pre[i]; 27 } 28 29 long long res = -LLONG_MAX; 30 multiset<long> history; 31 for (int i = a; i < n + 1; i++) { 32 if (i > b) 33 history.erase(history.find(pre[i - b - 1])); 34 35 history.insert(pre[i - a]); 36 res = max(res, pre[i] - *(history.begin())); 37 } 38 39 cout << res << "\n"; 40 } 41 42 int main() 43 { 44 ios::sync_with_stdio(0); 45 cin.tie(0); 46 solve(); 47 }