Cod sursa(job #369530)

Utilizator vladiiIonescu Vlad vladii Data 28 noiembrie 2009 17:19:54
Problema Secventa 2 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
int main() {
    fstream f1, f2;
    deque<pair<long long, long long> > deq;
    long long n, k, elem[50001], sum[50001], i, j, max=-1250075002, start, end;
    f1.open("secv2.in", ios::in);
    f1>>n>>k;
    f1>>elem[1]; sum[1]=elem[1];
    for(i=2; i<=n; i++) {
         f1>>elem[i];
         sum[i]=sum[i-1]+elem[i];
    }
    f1.close();
    for(i=k; i<=n; i++) {
         //calculez sum[i]-min(sum[j])
         //adaug i-k
         while(!deq.empty() && deq.back().first>sum[i-k+1]) {
              deq.pop_back();
         }
         deq.push_back(make_pair(sum[i-k+1], i-k+1));
         if(sum[i]-deq.front().first>max) {
              max=sum[i]-deq.front().first;
              start=deq.front().second+1;
              end=i;
         }
    }
    f2.open("secv2.out", ios::out);
    if(n==k) { f2<<1<<" "<<n<<" "<<sum[n]<<endl; }
    else { f2<<start<<" "<<end<<" "<<max<<endl; }
    f2.close();
    return 0;
}