Cod sursa(job #704013)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 2 martie 2012 15:58:55
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <fstream>
#include <deque>
#define N 50010

using namespace std;

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

deque<int> D;

int n,s[N],i,k,x,st,fn,maxi=-999999999;

void push(int i) {
    while (!D.empty() && s[i]<=s[D.back()]) D.pop_back();
    D.push_back(i);
}
int top() {
    if (!D.empty()) return D.front();
    return 0;
}

int main() {
    f >> n >> k;
    for (i=1;i<=n;i++) {
        f >> s[i];
        s[i]+=s[i-1];
    }
    for (i=k;i<=n;i++) {
        push(i-k);
        if (s[i]-s[top()]>maxi) {
            maxi=s[i]-s[top()];
            st=top()+1;fn=i;
        }
    }
    g << st << ' ' << fn << ' ' << maxi << '\n';
    f.close();g.close();
    return 0;
}