Cod sursa(job #2776533)

Utilizator AACthAirinei Andrei Cristian AACth Data 20 septembrie 2021 09:11:24
Problema Secventa 2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("secv2.in");
ofstream g("secv2.out");
#define cin f
#define cout g
//#define int long long
const int Max = 1e5 + 1;
void nos()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}
int n,k,w;
int sp[Max];
void read()
{
	f>>n>>k;
	int i;
	for(i=1;i<=n;i++)
	{
		int x;
		f>>x;
		sp[i] = sp[i - 1] + x;
	}
}
void solve()
{
	deque < pair < int , int > > dq;
	//first -->sp val
	//second --> del time
    int i;
    int ans = INT_MIN;
    int left,right;
    for(i = k;i<=n;++i)
    {
    	int add_this = sp[i - k ];
    	while(!dq.empty() and dq.back().first > add_this)
    		dq.pop_back();
    	dq.push_back({add_this,i});
    	//while(!dq.empty() and i - dq.front().second + 1 > w)
    	//	dq.pop_front();
    	if(ans < sp[i] - dq.front().first)
    	{
    		ans = sp[i] - dq.front().first;
    		left = dq.front().second;
    		right = i;
    	}
    }
    g<<left<<' '<<right<<' '<<ans;
}
void restart()
{

}
int32_t main()
{
    nos();

        read();
        solve();
        restart();
    
    return 0;
}