Cod sursa(job #7013)

Utilizator alle_forever13Alexandra Retegan alle_forever13 Data 21 ianuarie 2007 11:47:27
Problema Elimin Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda 1, Clasa a 10-a Marime 1.73 kb
#include<stdio.h>

#define input "elimin.in"

#define output "elimin.out"

#define dim 201

void qsort2(long p,long q);

void qsort1(long p,long q);

int divide2(long p,long q);

int divide1(long p,long q);

void rezolva();

long n, m, r, c, a[dim][dim], suma[3][dim], s, max;

int main()
{
	FILE *in, *out;

	in = fopen (input, "r");

	out = fopen (output, "w");

	long i, j;

	fscanf(in, "%ld%ld%ld%ld", &n, &m, &r, &c);

	for(i=1; i<=n; ++i)

		for(j=1; j<=m; ++j)
		{
			fscanf(in, "%ld", &a[i][j]);

			s+=a[i][j];
		}

	for(i=1; i<=n; ++i)

		for(j=1; j<=m; ++j)

			suma[1][i]+=a[i][j];

	for(j=1; j<=m; ++j)

		for(i=1; i<=n; ++i)

			suma[2][j]+=a[i][j];

	qsort1(1,n);

	qsort2(1,m);

	rezolva();

	fprintf(out, "%ld", s);

	return 0;

}


void qsort1(int p,int q)
{
	long m=divide1(p,q);

	if(m-1>p)

		qsort1(p,m-1);

	if(m+1<q)

		qsort1(m+1,q);
}

int divide1(int p,int q)
{
	long st=p, dr=q, x=suma[1][p];

	while(st<dr)
	{
		while(st<dr && suma[1][dr]>=x)

			dr--;

		suma[1][st]=suma[1][dr];

		while(st<dr &&suma[1][st]<=x)

			st++;

		suma[1][dr]=suma[1][st];
	}

	suma[1][st]=x;

	return st;


}

void qsort2(int p,int q)
{
	long m=divide2(p,q);

	if(m-1>p)

		qsort2(p,m-1);

	if(m+1<q)

		qsort2(m+1,q);
}

int divide2(int p,int q)
{
	long st=p, dr=q, x=suma[1][p];

	while(st<dr)
	{
		while(st<dr && suma[1][dr]>=x)

			dr--;

		suma[2][st]=suma[2][dr];

		while(st<dr &&suma[2][st]<=x)

			st++;

		suma[2][dr]=suma[2][st];
	}

	suma[2][st]=x;

	return st;


}


void rezolva()
{
	long i;

	for(i=1; i<=c; ++i)

		s-=suma[1][i];

	for(i=1; i<=r; ++i)

		s-=suma[2][i];

}