Pagini recente » Cod sursa (job #1564237) | Cod sursa (job #2618953) | Cod sursa (job #3288710) | Cod sursa (job #3135608) | Cod sursa (job #1122160)
/*
/// 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;
}