Pagini recente » Cod sursa (job #769297) | Cod sursa (job #2599815) | Cod sursa (job #1820903) | Cod sursa (job #2521023) | Cod sursa (job #2846758)
#include <bits/stdc++.h>
#define ull unsigned long long
#define FILES freopen("secv2.in","r",stdin);\
freopen("secv2.out","w",stdout);
#define CMAX 15485863
#define fastio std::ios_base::sync_with_stdio(NULL),cin.tie(NULL),cout.tie(NULL);
#define mp make_pair
#define INF 1e18
#define mod 1000000007
#define ll long long
#define SMAX 300
#define MAX 50000
#define pb push_back
#define add emplace_back
#define void inline void
using namespace std;
int n,v[MAX+5],sm[MAX+5],m;
vector<int> go[MAX+5];
int main()
{
fastio
FILES
cin >> n >> m;
for(int i = 1;i <= n; ++i)
cin >> v[i],sm[i] += sm[i-1] + v[i];
int best = sm[m],start = 1,endp = m;
deque<pair<int,int>> dq;
for(int i = 2;i <= m; ++i)
go[i+m-1].add(i);
dq.push_back(mp(best,1));
for(int i = m + 1;i <= n; ++i)
{
for(auto j : go[i])
{
int x = sm[i] - sm[j-1];
while(!dq.empty() && x > dq.back().first + sm[i] - sm[dq.back().second+m-1]) dq.pop_back();
dq.push_back(mp(x,j));
}
go[i].clear();
int sum = dq.front().first + sm[i] - sm[dq.front().second+m-1];
if(sum > best) best = sum,start = dq.front().second,endp = i;
go[i+m-1].add(i);
}
cout << start << ' ' << endp << ' ' << best;
}