Cod sursa(job #952665)

Utilizator primulDarie Sergiu primul Data 23 mai 2013 19:41:57
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <fstream>
#include <deque>
 
using namespace std;
 
const int MAX = 500005;
 
int N, K, index, ans = -35000, start, stop;
int V[MAX];
string S;
deque<int> dq;
 
inline int citire() {
    while(!isdigit(S[index]) && S[index] != '-') index++;
    int val = 0, semn = 1;
    if(S[index] == '-') semn = -1, index++;
    while(index < S.length() && isdigit(S[index]))
        val = 10 * val + S[index++] - '0';
    return semn * val;
}
 
int main() {
    ifstream in("secventa.in");
    in >> N >> K; in.get();
    getline(in, S); index = 0;
    for(int i = 1; i <= N; i++) {
        V[i] = citire();
        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();
}