Cod sursa(job #1729670)

Utilizator liviu23Liviu Andrei liviu23 Data 15 iulie 2016 13:59:50
Problema Secventa 2 Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <deque>
#include <fstream>
#include <iostream>
#define ll long long
using namespace std;

deque<int> d;
int n,k;
ll s[50005];

int main()
{
    ifstream fin("secv2.in");
    ofstream fout("secv2.out");
    fin>>n>>k;
    int m;
    for(int i=1;i<=n;i++) {
        fin>>m;
        s[i]=s[i-1]+m;
    }
    ll mx=-25000*(k+1);
    int st=1,dr=k;
    for(int i=1;i<=n;i++) {
        d.push_back(i);
        while(!d.empty()&&d.size()>k&&s[d.back()]<=s[d.front()-1])
            d.pop_front();
        if(d.size()>=k&&s[d.back()]-s[d.front()-1]>mx) {
            mx=s[d.back()]-s[d.front()-1];
            st=d.front();
            dr=d.back();
        }
    }
    fout<<st<<" "<<dr<<" "<<mx;
    return 0;
}