Pagini recente » Cod sursa (job #1418161) | Cod sursa (job #803612) | Cod sursa (job #2065471) | Cod sursa (job #2146877) | Cod sursa (job #3149048)
#include <bits/stdc++.h>
using namespace std;
int n, k;
vector <int> v;
deque <int> maxSum;
int main()
{
ios_base :: sync_with_stdio(0);
cin.tie(0);
freopen("secv2.in", "r", stdin);
freopen("secv2.out", "w", stdout);
cin >> n >> k;
v.resize(n + 1);
for(int i = 1; i <= n; i ++)
{
cin >> v[i];
v[i] += v[i - 1];
}
for(int i = 1; i <= k; i ++)
{
while(!maxSum.empty() && v[i] > maxSum.back())
maxSum.pop_back();
maxSum.push_back(v[i]);
}
int minSum = 0, index = 0, st = 1, dr = k, ans = maxSum.front();
for(int i = k + 1; i <= n; i ++)
{
if(v[i - k] < minSum)
{
minSum = v[i - k];
index = i - k;
}
if(!maxSum.empty() && v[i - k] == maxSum.front())
maxSum.pop_front();
while(!maxSum.empty() && v[i] > maxSum.back())
maxSum.pop_back();
maxSum.push_back(v[i]);
// cout << i << " " << maxSum.front() << " " << minSum << "\n";
if(maxSum.front() - minSum > ans)
{
ans = maxSum.front() - minSum;
st = index + 1;
dr = i;
}
}
cout << st << " " << dr << " " << ans;
return 0;
}