Cod sursa(job #1454009)

Utilizator ducnthbducnthb ducnthb Data 25 iunie 2015 11:50:19
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <fstream>
#include <sstream>
#include <deque>

using namespace std;
const char FIN[] = "secventa.in";
const char FOU[] = "secventa.out";
const int MAXN = 500010;
int  n, k, a[MAXN], aMax = -31000, r = 0;
deque<int> dq;
string s;

int main(){
    ifstream fi(FIN);
    ofstream fo(FOU);
    fi >> n >> k; fi.ignore(255,'\n');
    getline(fi,s);
    istringstream iss(s);
    int i = 0;
    while(iss >> a[++i]);
    for (int i = 1; i <= n; i++){
        while (!dq.empty() && a[i] <= a[dq.back()]) dq.pop_back();
        dq.push_back(i);
        if (dq.front() == i-k) dq.pop_front();
        if  (i >= k && aMax < a[dq.front()]){ ;
            aMax = a[dq.front()];
            r = i;
        }
    }
    fo << r-k+1 << ' ' << r << ' ' << aMax << endl;
    return  0;
}