Cod sursa(job #424644)

Utilizator digistyl3Janos Levai digistyl3 Data 25 martie 2010 00:07:17
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
/* 
 * File:   main.cpp
 * Author: Johnny
 *
 * Created on March 24, 2010, 11:36 PM
 */

#include <stdlib.h>
#include <deque>
#include <iostream>
#include <fstream>

using namespace std;

struct Pair {
    short value;
    int pos;

    Pair(short value, int pos) {
        this->value = value;
        this->pos = pos;
    }
};

int main(int argc, char** argv) {
    deque<Pair> deq;

    ifstream f("secventa.in");
    short temp;
    int n, k;
    
    f >> n;
    f >> k;
    for (int i = 1; i <= k; ++i) {
        f >> temp;
        while (!deq.empty() && deq.front().value > temp)
            deq.pop_front();
        deq.push_front(Pair(temp, i));
    }

    int maxBase = deq.back().value;
    int endPos = k;

    for (int i = k + 1; i <= n; ++i) {
        if (i - deq.back().pos == k)
            deq.pop_back();

        f >> temp;
        while (!deq.empty() && deq.front().value > temp)
            deq.pop_front();
        deq.push_front(Pair(temp, i));

        if (deq.back().value > maxBase) {
            maxBase = deq.back().value;
            endPos = i;
        }
    }
    f.close();

    ofstream g("secventa.out");
    g << endPos - k + 1 << ' ' << endPos << ' ' << maxBase;
    g.close();
    return (EXIT_SUCCESS);
}