Cod sursa(job #1456231)

Utilizator Salomia_Adrian_325CCSalomia Adrian Salomia_Adrian_325CC Data 30 iunie 2015 08:43:25
Problema Secventa 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <stdio.h>
#include <stdlib.h>

int main() {
	FILE *f1 = fopen("secv2.in", "r");
	FILE *f2 = fopen("secv2.out", "w");

	int n, k;
	fscanf(f1, "%d%d", &n, &k);

	int *v = (int *) malloc ((n+1) * sizeof(int));
	int i, j;
	for(i = 1;i <= n;i++)
		fscanf(f1, "%d", &v[i]);

	int *din = (int *) malloc ((n+1) * sizeof(int));
	int *ind_sf = (int *) malloc ((n+1) * sizeof(int));

	din[n-k+1] = 0;
	for(i = n-k+1;i <= n;i++)
		din[n-k+1] += v[i];
	ind_sf[n-k+1] = n;
	int s; 
	int s_max = din[n-k+1], i_max = n-k+1;
	for(i = n-k;i >= 1;i--) {
		// if(ind_sf[i+1] - i != k) {
		// 	din[i] = v[i] + din[i+1];
		// 	ind_sf[i] = ind_sf[i+1];	
		// 	if(s_max < din[i]) {
		// 		s_max = din[i];
		// 		i_max = i;
		// 	}
		// 	continue;	
		// }
		if(2*k >= ind_sf[i+1] - i) {
			s = v[i] + din[i+1];
			for(j = i+k;j <= ind_sf[i+1];j++)
				s -= v[j];
		}
		else {
			s = v[i];
			for(j = i+1;j < i+k;j++)
				s += v[j];
		}
		if(s > v[i] + din[i+1]) {
			din[i] = s;
			ind_sf[i] = i+k-1;
		}
		else {
			din[i] = v[i] + din[i+1];
			ind_sf[i] = ind_sf[i+1];
		}

		if(s_max < din[i]) {
			s_max = din[i];
			i_max = i;
		}	
	}


	fprintf(f2, "%d %d %d\n", i_max, ind_sf[i_max], s_max);

	fclose(f1);
	fclose(f2);
	return 0;
}