Cod sursa(job #1346224)

Utilizator fluture.godlikeGafton Mihnea Alexandru fluture.godlike Data 18 februarie 2015 08:57:47
Problema Secventa 2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <stdio.h>
#define NMAX 50023
#define lim 25023
FILE *fin, *fout;
int n, k, v[NMAX], maxim = -lim, p1, p2;
struct nr
{
	int pos;
	int val;
} dyn[NMAX], dyn2[NMAX];
int main()
{
	fin = freopen("secv2.in", "r", stdin);
	fout = freopen("secv2.out", "w", stdout);
	scanf("%d %d", &n, &k);
	for(int i = 1; i<= n; i++)
	{
		scanf("%d", &v[i]);
	}
	dyn[1].val = v[1];
	for(int i = 2; i<= n; i++)
	{
		if(dyn[i-1].val > 0)
		{
			dyn[i].val = dyn[i-1].val + v[i];
			dyn[i].pos = dyn[i-1].pos;
		}
		else
		{
			dyn[i].val = v[i];
			dyn[i].pos = i;
		}
	}
	for(int i = 2; i<= n; i++) v[i] += v[i-1];
	for(int i = k; i<= n; i++)
	{
		dyn2[i].val = v[i] - v[i-k];
		dyn2[i].pos = i-k+1;
		if(dyn[i-k].val > 0)
		{
			dyn2[i].val += dyn[i-k].val;
			dyn2[i].pos = dyn[i-k].pos;
		}
		if(dyn2[i].val > maxim)
		{
			maxim = dyn2[i].val;
			p1 = dyn2[i].pos;
			p2 = i;
		}
	}
	printf("%d %d %d\n", p1, p2, maxim);
	fclose(fin);
	fclose(fout);
	return 0;
}