Cod sursa(job #951253)

Utilizator SRaduRadu Szasz SRadu Data 19 mai 2013 20:35:10
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <fstream>
#include <deque>

using namespace std;

const int MAX = 500005;

int N, K, ans = -35000, start, stop;
int V[MAX];
deque<int> dq;

int main() {
    ifstream in("secventa.in"); 
    in >> N >> K;
    for(int i = 1; i <= N; i++) {
        in >> V[i];
        while(!dq.empty() && V[dq.back()] > V[i]) dq.pop_back();
        while(!dq.empty() && dq.front() <= i - K) dq.pop_front();
        dq.push_back(i);
        if(i >= K && V[dq.front()] > ans) {
            ans = V[dq.front()];
            start = i - K + 1;
            stop = i;
        }
    } in.close();
    ofstream out("secventa.out"); out << start << " " << stop << " " << ans << "\n"; out.close();
}