Cod sursa(job #42805)

Utilizator SpiriSpiridon Alexandru Spiri Data 29 martie 2007 15:36:57
Problema Secventa Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <fstream>
#include <iostream>
#include <deque>
#include <set>
#include <vector>
#define INF 32000
using namespace std;

ifstream fin ("secventa.in");
ofstream fout ("secventa.out");

int n, k;
vector<int> a;
int s, f, b;

int main()
{
    fin >> n >> k;
    int val;
    for ( int i = 1; i <= n; i++ )
    {
        fin >> val;
        a.push_back(val);
    }  
    
    b = 0;
    deque<int> q;
    int ma = 0;
    int mi = INF;
    for ( int i = 0; i < k; i++ )
    {
        //fout << a[i] << " ";
        q.push_back(a[i]);
        if ( a[i] < mi )
        {
            mi = a[i];
        }    
    }
    b = mi;
    s = 1;
    f = k;  
    bool ok = true;
    int p = 0;
    int u = k - 1;
    while(ok)
    {
        if ( u + 1 < n )
        {
            q.push_back(a[u+1]);
            if ( a[u+1] < mi )
            {
                mi = a[u+1];
            }    
            if ( mi > b )
            {
                b = mi;
                s = p + 1;
                f = u + 1;
            }    
            u++;
            deque<int>::iterator it;
        }    
        if ( u == n - 1 )
        {  
            q.pop_front();
            p++;
            while ( u >= p + k )
            {
                q.pop_back();
                u--;
            }   
            
            mi = INF;
            deque<int>::iterator it;
            for ( it = q.begin(); it != q.end(); it++ )
            {
                if ( *it < mi )
                {
                    mi = *it;
                }    
            }   
            if ( mi > b )
            {
                b = mi;
                s = p + 1;
                f = u + 1;
            }  
            if ( p == n - k )
            {
                break;
            }  
        }       
    }    
       
    fout << s << " " << f << " " << b;
        
    fin.close();
    fout.close();
    return 0;
}