Cod sursa(job #45922)

Utilizator chermanCorina Herman cherman Data 2 aprilie 2007 08:13:39
Problema Secventa 2 Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <fstream>
#include <iostream>

using namespace std;

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

int n, a[50000], k, ktmp=0;
int seqStart = 0, seqEnd =-1;

    int s=0;
    int d=n-1;

    int temp1,temp2,ss,dd;

    int s1=0;
    int d1=1;

void read()
{
    in >> n >> k;
    for ( int i = 0; i < n; ++i )
        in >> a[i];
}

int maxim()
    {
	s=0;
    d=n-1;


    s1=0;
    d1=1;
    while(d-s+1>=4 && (d1!=d||s1!=s))
    {
       s1=s;
       d1=d;
        if (a[s]<0 && a[d]<0)
        {
         if (a[s]<=a[d])
         {
             s++;
             //cout<<a[s-1]<<"**"<<a[d]<<endl;
         }
         else
         if (a[s]>a[d]) d--;
        }
        else
        if (a[s]<0) s++;
        else
        if (a[d]<0) d--;
        else
        {
            temp1=0;
            ss=s;
            while(d-ss+1>=4 && temp1>=0)
            {
                temp1=a[ss];
                ss++;
            }
            if (temp1<0)
            {
             temp2=0;
             dd=d;
             while(dd-s+1>=4 && temp2>=temp1)
             {
                temp2=a[dd];
                dd--;
             }
            }

            if (temp1<0 && temp2<0)
            {
             if (temp1<=temp2)  d=dd;
             if (temp1>temp2) s=ss;
            }
            else
            if (temp1<0) s=ss;
            else
            if (temp2<0) d=dd;
        }
    }
        }
int suma()
{
    int sum=0;
    for(int i=s;i<=d;i++)
    sum+=a[i];
    return sum;
}

void suma2()
{
    int sum=-65535;
    for(int xx=k;xx<n;xx++)
    {
    for(int i=0;i<n-xx;i++)
    {
     int sum1=-65535;
     for(int j=i;j<=i+xx;j++)
     {
      if (sum1!=-65535) sum1+=a[j];
      else sum1=a[j];
     }
     if (sum1>sum)
     {
         sum=sum1;
         s=i;
         d=i+xx;
     }
    }
    }
    cout<<s+1<<" "<<d+1<<" "<<sum;
    out<<s+1<<" "<<d+1<<" "<<sum;
}


int main()
{
    read();
    /*
    maxim();
    cout<<s+1<<" "<<d+1<<" " <<suma();
    out<<s+1<<" "<<d+1<<" " <<suma();
    */
    suma2();
	return 0;
}