Cod sursa(job #390030)
#include <fstream>
#define NMAX 52000
#define INF 1000000000
using namespace std;
int Sir[NMAX], N, K, SumeK[NMAX], Sum, bestSum, bestSt, bestFi, Inc, Final;
void Citire(void)
{
ifstream fin("secv2.in");
int i;
bestSum = -INF;
fin >>N >>K;
for (i = 1; i <= N; i++)
fin >>Sir[i];
for (i = 1; i <= K; i++)
SumeK[i] = SumeK[i-1] + Sir[i];
if (SumeK[i] > bestSum)
bestSum = SumeK[i - 1], bestSt = i - K , bestFi = i - 1;
for(; i <= N; i++)
{
SumeK[i] = SumeK[i-1] + Sir[i] - Sir[i - K];
if (SumeK[i] > bestSum)
bestSum = SumeK[i], bestSt = i - K + 1, bestFi = i;
}
fin.close();
}
void Rezolva(void)
{
int i, sum = -INF;
for (i = 1; i <= N - K; i++)
{
if (sum + Sir[i] > Sir[i])
{
sum += Sir[i];
Final = i;
}
else
{
sum = Sir[i];
Final = Inc = i;
}
if (sum + SumeK[i + K] > bestSum) bestSum = sum + SumeK[i + K], bestSt = Inc, bestFi = Final + K;
}
}
void Afiseaza()
{
ofstream fout("secv2.out");
fout <<bestSt <<' ' <<bestFi <<' ' <<bestSum;
fout.close();
}
int main()
{
Citire();
Rezolva();
Afiseaza();
return 0;
}