Pagini recente » Cod sursa (job #269270) | Cod sursa (job #7013)
Cod sursa(job #7013)
#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];
}