Cod sursa(job #867493)

Utilizator superman_01Avramescu Cristian superman_01 Data 29 ianuarie 2013 19:10:10
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<cstdio>
#include<deque>
#define NMax 50000005
 
FILE *f=fopen("secventa.in","r");
FILE *g=fopen("secventa.out","w");
using namespace std;
 
deque <int> Q;
int v[NMax];
long long s,smax;
int n,k,start,finish,cont;
void read()
{
     
    int i,j;
    fscanf(f,"%d%d",&n,&k);
    for(i=1;i<=n;i++)
       fscanf(f,"%d",&v[i]);
     
}
void solve()
{
    int i,j;
	smax=-20000000;
    for(i=1;i<=n;i++)
    {
        while(Q.size()&&v[Q.back()]>=v[i])
        Q.pop_back();
         
        Q.push_back(i);
     
        if(Q.front()==(i-k) )
             Q.pop_front();
        if(i>=k)
        {  
			s+=v[Q.front()];
			
          if(s>smax)

		  {
			  start=Q.front();
			  finish=i;
			  cont=v[Q.front()];
			  s=0;
		  }		
		}		  
    }
     
}
void write()
{
    fprintf(g,"%d %d %d",start,finish,cont);
}
 
int main()
{
    int i,j;
    read();
    solve();
    write();
    return 0;
}