Cod sursa(job #1378913)

Utilizator PaueyPaula Nicoleta Gradu Pauey Data 6 martie 2015 15:03:57
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <deque>
#include <fstream>
#include <iostream>
#include <sstream>
#include <string>
using namespace std;

const int MAXN = 500005;

deque<int> dq;
int v[MAXN];
string s;

int main()
{
    ifstream cin("secventa.in");
    ofstream cout("secventa.out");
    int N, K, maxb = -40000, st = 0, dr = 0;
    cin >> N >> K;
    getline(cin, s);
    getline(cin, s);
    stringstream ss;
    ss << s;
    for(int i = 1; i <= N; ++i) {
      ss >> v[i];
      while(!dq.empty() && v[dq.back()] > v[i])
         dq.pop_back();
      if(!dq.empty() && i - dq.front() + 1 > K)
         dq.pop_front();
      dq.push_back(i);
      if(i >= K && v[dq.front()] > maxb) {
         maxb = v[dq.front()];
         dr = i;
         st = i - K + 1;
      }
    }
    cout << st << " " << dr << " " << maxb;
    return 0;
}