Pagini recente » Cod sursa (job #1055930) | Cod sursa (job #541956) | Cod sursa (job #171225) | Cod sursa (job #2363356) | Cod sursa (job #164950)
Cod sursa(job #164950)
#include<stdio.h>
#define INPUT "secv2.in"
#define OUTPUT "secv2.out"
#define NMAX 50001
FILE *fin=fopen(INPUT, "r"),*fout=fopen(OUTPUT, "w");
long N, K, PIMax, PFMax, pozPoz, sumNeg;
long a[ NMAX ], sum[ NMAX ], SMax[ NMAX ], PMax[ NMAX];
void readValues();
void solveFunction();
void printSolution();
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 - K] + a[ i ];
}
}
void solveFunction()
{
long pozPoz;
SMax[ K ] = sum[ K ];
PMax[ K ] = 1;
sumNeg = 0;
pozPoz = K;
for(long i = K+1; i <= N; ++i)
{
if(a[ i ] > 0)
{
if(SMax[ pozPoz ] + a[ i ] +sumNeg > sum[ i ])
{
SMax[ i ] = SMax[ pozPoz] + a[ i ] + sumNeg;
PMax[ i ] = PMax[ pozPoz];
}
else
{
SMax[ i ] = sum[ i ];
PMax[ i ] = i - K + 1;
}
pozPoz = i;
}
else
{
if(SMax[ i - 1] + a[ i ] < sum[ i ])
{
SMax[ i ] = sum[ i ];
PMax[ i ] = i - K + 1;
}
else
sumNeg += a[ i ];
}
}
printSolution();
}
void printSolution()
{
long long VMax = SMax[ K ];
long pozitie, poz2;
for(long i = K + 1; i <= N; ++i)
if(VMax < SMax[ i ])
{
VMax = SMax[ i ];
pozitie = PMax[ i ];
poz2 = i;
}
fprintf(fout, "%ld %ld %lld\n", pozitie, poz2, VMax);
}