Cod sursa(job #2050134)

Utilizator radu.leonardoThe Doctor radu.leonardo Data 27 octombrie 2017 23:01:05
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.6 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("secv2.in");
ofstream g("secv2.out");

int N,K,Ans=INT_MIN;
int Left,Right;
int V[50010];
deque<int> DQ;

int main() {
    f>>N>>K;
    for(int i=1; i<=N; i++)
        f>>V[i],
        V[i]+=V[i-1];

    for(int i=0; i<=N; i++) {
        while(!DQ.empty() && V[i]<=V[DQ.back()]) DQ.pop_back();
        DQ.push_back(i);
        if(i+K<=N)
            if(V[i+K]-V[DQ.front()]>Ans) {
                Ans=V[i+K]-V[DQ.front()];
                Left=DQ.front()+1;
                Right=i+K; } }
    g<<Left<<' '<<Right<<' '<<Ans; }