Cod sursa(job #394619)

Utilizator AnteusPatrascoiu Mihai Anteus Data 11 februarie 2010 11:31:07
Problema Secventa 2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <stdio.h>
FILE *f=fopen ("secv2.in", "r");
FILE *g=fopen ("secv2.out", "w");
int v[50001],n,k,i,poz[2][50001],k2,x,l,sw,j;

void shell (int n, int v[2][50001]) {
int i,sw,inj=n;
while (inj>1)
{
	inj/=2;
	do
	{
		sw=0;
		for (i=1;i<=n-inj;i+=inj)
			if (v[0][i]<v[0][i+inj])
			{
				v[0][i]=v[0][i]^v[0][i+inj];
				v[0][i+inj]=v[0][i]^v[0][i+inj];
				v[0][i]=v[0][i]^v[0][i+inj];
				sw=1;
				
				v[1][i]=v[1][i]^v[1][i+inj];
				v[1][i+inj]=v[1][i]^v[1][i+inj];
				v[1][i]=v[1][i]^v[1][i+inj];

			}
	}
	while (sw);
}
}


int main() {
fscanf (f, "%d%d", &n, &k);
for (i=1;i<=n;i++)
{
	fscanf (f, "%d", &x);
	if (v[i-1]+x>0)
		v[i]=v[i-1]+x;
	else
		v[i]=0;
	poz[0][i]=v[i];
	poz[1][i]=i;
}

shell (n, poz);

while (1)
{
	l++; k2=0; j=poz[1][l];
	
	while (v[j])
	{
		k2++;
		j--;
	}
	
	if (k2>=k)
		{
			fprintf (g, "%d %d %d", j+1, poz[1][l], v[poz[1][l]] );
			break;
		}
}
return 0;
}