Cod sursa(job #1122160)

Utilizator catalincraciunCraciun Catalin catalincraciun Data 25 februarie 2014 16:44:10
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.61 kb

/*
/// Craciun Catalin
///  Secv2
///   Programare dinamica
#include <fstream>
#include <iostream>
#include <map>

struct cheie{

    int LEFT, RIGHT;
};

#define NMax 50005
#define INF 0x3f3f3f

using namespace std;

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

unsigned int n,k;
int A[NMax];
long long S[NMax];
unsigned int st, dr, auxSt;

void pd()
{/*
    bool found=false;
    long long minim;
    unsigned int st, dr;
    long long bestSum;

    for (unsigned int i=1;i<=n;i++)
        S[i]=S[i-1]+A[i];

    dr=k;
    bestSum=S[k];

    for (unsigned int i=1;i<=n-k;i++)
    {
        if (S[i]<minim)
        {
            minim=S[i];
            st=i;
        }

        if (S[i+k]-minim>bestSum)
        {
            bestSum=S[i+k]-minim;
            st=i+k;
        }
    }

    g<<st+1<<' '<<dr<<' '<<bestSum<<'\n';
    g.close();

    int n , k , secv[50001] , poz_inc=0 , poz_sf , minim , best , i , x ;

    for ( i = 1 ; i <= n ; i ++ )
    {
        secv[i] = secv[i-1] + A[i] ;
    }

    poz_sf = k ;
    best = secv[k] ;

    for ( i = 1 ; i <= n - k ; i ++ )
    {
        if ( secv[i] < minim )
        {
            minim = secv[i] ;
            poz_inc = i ;
        }

        if ( secv[i+k] - minim > best )
        {
            best = secv[i+k] - minim ;
            poz_sf = i + k ;
        }
    }

    g << poz_inc + 1 << " " << poz_sf << " " << best ;
}

void citire()
{
    f>>n>>k;
    for (unsigned int i=1;i<=n;i++)
        f>>A[i];

    f.close();
}

int main()
{
    citire();
    pd();

    return 0;
}
*/


#include <stdio.h>
int a[50001],dk[50001],n,k,i,j;
long max,sfmax,lmax,ts,stmax,sfmax2,bigmax;
int main()
{
FILE *fin,*fout;
fin=fopen("secv2.in","rt");
fout=fopen("secv2.out","wt");
fscanf(fin,"%d %d",&n,&k);
for (i=1;i<=n;i++)
  fscanf(fin,"%d ",&a[i]);
i=k;
for (j=i;j>=1;j--)
  dk[i]+=a[j];
for (i=k+1;i<=n;i++)
  dk[i]=dk[i-1]-a[i-k]+a[i];
max=-2147483647;
for (i=k;i<=n;i++)
   if (dk[i]>max)
       { max=dk[i];
     sfmax=i;
     }
dk[sfmax-k]=a[sfmax-k];
for (i=sfmax-k-1;i>=1;i--)
    dk[i]=a[i]+dk[i+1];
max=-2147483647;
for (i=1;i<=sfmax-k;i++)
   if (dk[i]>max)
     { max=dk[i];
       stmax=i;
     }
if (max<0)
  stmax=sfmax-k+1;
dk[sfmax+1]=a[sfmax+1];
for (i=sfmax+2;i<=n;i++)
    dk[i]=a[i]+dk[i-1];
max=-2147483647;
for (i=sfmax+1;i<=n;i++)
   if (dk[i]>max)
     { max=dk[i];
       sfmax2=i;
     }
if (max>0)
  sfmax=sfmax2;
bigmax=0;
for (i=stmax;i<=sfmax;i++)
  bigmax+=a[i];
fprintf(fout,"%ld %ld %ld\n",stmax,sfmax,bigmax);
return 0;
}