Cod sursa(job #447627)

Utilizator sunmirrorSorin Stelian sunmirror Data 29 aprilie 2010 16:28:28
Problema Secventa 2 Scor 90
Compilator c Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <stdio.h>

#define IN_FILE "secv2.in"
#define OUT_FILE "secv2.out"

#define MAX_N 50000
#define MIN_SUM -1250000001

int N, K;
int numere[MAX_N + 1];

int max(int n1, int n2)
{
	return ((n1 > n2) ? n1 : n2);
}

int main(void)
{
	int i, j, sum_last_k;
	int max_sum, begin, end;	
	int S[MAX_N + 1], len[MAX_N + 1];

	FILE *fin, *fout;

        fin = fopen(IN_FILE, "r");
        fscanf(fin, "%d %d\n", &N, &K);
        for (i = 1; i <= N; i++)
        {
                fscanf(fin, "%d ", numere+i);
        }
        fclose(fin);

	len[K] = K;
	S[K] = 0;
	for (i = 1; i <= K; i++)
		S[K]+= numere[i];
	max_sum = MIN_SUM;

	for (i = K + 1; i <= N; i++)
	{
		if (len[i-1] == K)
		{
			if ( (S[i-1] + numere[i]) > (S[i-1] + numere[i] - numere[i-K]) )
			{
				len[i] = K + 1;
				S[i] = S[i-1] + numere[i];
			}
			else
			{
				len[i] = K;
				S[i] = S[i-1] + numere[i] - numere[i-K];
			}
		}
		else
		{
			if (numere[i - K] < 0)
			{
				sum_last_k = 0;
				for (j = i - K + 1; j <= i; j++)
					sum_last_k+= numere[j];
				if (sum_last_k > S[i - 1] + numere[i])
				{
					S[i] = sum_last_k;
					len[i] = K;
				}
				else
				{
					S[i] = S[i-1] + numere[i];
					len[i] = len[i-1] + 1;
				}
			}
			else
			{
				S[i] = S[i-1] + numere[i];	//aici ar putea fi eliminata un pic redundanta
				len[i] = len[i-1] + 1;
			}
		}

		if (S[i] > max_sum)
		{
			max_sum = S[i];
			end = i;		
			begin = i - len[i] + 1;	
		}
	}

        fout = fopen(OUT_FILE, "w");
        fprintf(fout, "%d %d %d\n", begin, end, max_sum);
        fclose(fout);

        return 0;
}