Pagini recente » Cod sursa (job #725740) | Cod sursa (job #2048205) | Cod sursa (job #587700) | Cod sursa (job #1372987) | Cod sursa (job #166151)
Cod sursa(job #166151)
#include<stdio.h>
#define INPUT "secv2.in"
#define OUTPUT "secv2.out"
#define INFI -2000000000
#define NMAX 50001
FILE *fin = fopen(INPUT, "r"), *fout = fopen(OUTPUT, "w");
long N, K;
long a[ NMAX ], sum[ NMAX ];
void readValues();
void solveFunction();
int main()
{
readValues();
solveFunction();
fclose(fin);
fclose(fout);
return 0;
}
void readValues()
{
fscanf(fin, "%ld %ld", &N, &K);
for(long i = 1; i <= N; ++i)
{
fscanf(fin, "%ld", &a[ i ]);
if(i <= K)
sum[ i ] = sum[ i - 1] + a[ i ];
else
sum[ i ] = sum[ i - 1 ] + a[ i ] - a[ i - K ];
}
}
void solveFunction()
{
long SMax, PIMax, PFMax, SNou, MaxMin, PMm;
SMax = sum[ K ];
PIMax = 1;
PFMax = K;
for(long i = K + 1; i <= N; ++i)
{
if( a[ i ] < 0)
{
SNou = 0;
MaxMin = INFI;
PMm = -1;
while( i <= N && a[ i ] < 0)
{
SNou += a[ i ];
if(sum[ i ] > MaxMin)
{
MaxMin = sum[ i ];
PMm = i;
}
++i;
}
if(i <= N)
{
if(SMax + SNou + a[ i ]< sum[ i ])
{
SMax = sum[ i ];
PIMax = i - K + 1;
PFMax = i;
}
else
{
SMax += SNou;
SMax += a[ i ];
PFMax = i;
}
}
else
{
if(MaxMin > SMax)
{
SMax = MaxMin;
PIMax = PMm - K + 1;
PFMax = PMm;
}
}
}
else
{
if(SMax + a[ i ] < sum[ i ])
{
SMax = sum[ i ];
PIMax = i - K + 1;
PFMax = i;
}
else
{
SMax += a[ i ];
PFMax = i;
}
}
}
fprintf(fout, "%ld %ld %ld\n", PIMax, PFMax, SMax);
}