Cod sursa(job #1164095)

Utilizator DysKodeTurturica Razvan DysKode Data 1 aprilie 2014 20:44:52
Problema Secventa 2 Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream>
using namespace std;    //Rezolvare in ON^2

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

int v[50010],s[50010],a,b,poz1,poz2,x,y,n,k,maxi,ok,tot;

void citirea()
{
    int i;
    fin>>n>>k;
    tot=1<<(31);
    for(i=1 ; i<=n ; i++)
    {
        fin>>v[i];
        s[i]=v[i]+s[i-1];
        if(v[i]>tot)
        {
            tot=v[i];
            poz1=i;
        }
    }
}

void rezolvarea()
{
    int i,j;
    if(k>1)
        for(i=1 ; i<=n-k && k>1 ; i++)
        {
            while(poz2-i>k && s[i+1]>s[i]+10)
                i++;
            for(j=i+k ; j<=n ; j++)
            {
                ok=0;
                if(s[j]-s[i-1]>=maxi)
                {
                    while (s[j+1]>=s[j])
                        j++;
                    maxi=s[j]-s[i-1];
                    poz1=i;
                    poz2=j;
                    ok=1;
                }
            }
            if(ok)
                i=poz2-1;
        }
}

int main()
{
    maxi=1<<(31);
    citirea();
    rezolvarea();
    if(k>1)
        fout<<poz1<<" "<<poz2<<" "<<maxi;
    else if(k==1)
        fout<<poz1<<" "<<poz1<<" "<<tot;

fin.close();
fout.close();
return 0;
}