Cod sursa(job #161887)

Utilizator andreisfrentSfrent Andrei andreisfrent Data 18 martie 2008 22:15:35
Problema Secventa 2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <stdio.h>
#include <stdlib.h>

#define N 50000
int n,k;
int ind[N];
long long sp[N];

void init_ind()
{
	for(int i=1;i<=n;++i) ind[i]=i;
}
void citeste()
{
	freopen("secv2.in","r",stdin);
	scanf("%d%d",&n,&k);
	int x;
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&x);
		sp[i]=sp[i-1]+x;
	}
	fclose(stdin);
}
int f_cmp(const void *a, const void *b)
{
	int ia = *((int*)a);
	int ib = *((int*)b);
	return sp[ia]-sp[ib];
}
int main()
{
	
	citeste();
	init_ind();
	qsort(ind+1,n,sizeof(int),f_cmp);
	int i(1),j(n);
	while(1)
	{
		if(ind[j]-ind[i] + 1>=k) break;
		if(sp[ind[j]]-sp[ind[j-1]] < sp[ind[i+1]]-sp[ind[i]]) --j;
		else ++i;
	}
	freopen("secv2.out","w",stdout);
	printf("%d %d %lld\n", ind[i]+1, ind[j], sp[ind[j]] - sp[ind[i]]);
	fclose(stdout);
	
	return 0;	
}