Pagini recente » Cod sursa (job #3179138) | Cod sursa (job #1622578) | Cod sursa (job #945318) | Cod sursa (job #268704) | Cod sursa (job #1122200)
/// Craciun Catalin
/// Secv2
/// www.infoarena.ro/problema/secv2
/// Programare dinamica
#include <fstream>
#include <iostream>
#define NMax 50005
#define MIN_INF -1<<31
using namespace std;
ifstream f("secv2.in");
ofstream g("secv2.out");
int a[NMax],dk[NMax],n,k,i,j;
long maxim,sfmax,lmax,ts,stmax,sfmax2,bigmax;
void afisare()
{
g<<stmax<<' '<<sfmax<<' '<<bigmax<<'\n';
}
void programareDinamica()
{
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];
maxim=MIN_INF;
for (i=k;i<=n;i++)
if (dk[i]>maxim)
{ maxim=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];
maxim=MIN_INF;
for (i=1;i<=sfmax-k;i++)
if (dk[i]>maxim)
{
maxim=dk[i];
stmax=i;
}
if (maxim<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];
maxim=MIN_INF;
for (i=sfmax+1;i<=n;i++)
if (dk[i]>maxim)
{
maxim=dk[i];
sfmax2=i;
}
if (maxim>0)
sfmax=sfmax2;
bigmax=0;
for (i=stmax;i<=sfmax;i++)
bigmax+=a[i];
}
void citire()
{
f>>n>>k;
for (i=1;i<=n;i++)
f>>a[i];
}
int main()
{
citire();
programareDinamica();
afisare();
return 0;
}