Pagini recente » Cod sursa (job #1927128) | Cod sursa (job #1925044) | Cod sursa (job #2373536) | Cod sursa (job #2033271) | Cod sursa (job #60007)
Cod sursa(job #60007)
#include <cstdio>
#include <iostream>
#define max 480
FILE *in = fopen("elimin.in","r"), *out = fopen("elimin.out","w");
int n, m, r, c;
int a[max][max];
int eliminate[max] = {0};
int s = 0;
void read()
{
fscanf(in, "%d %d %d %d", &m, &n, &r, &c);
if ( m <= n )
{
for ( int i = 1; i <= m; ++i )
for ( int j = 1; j <= n; ++j )
fscanf(in, "%d" , &a[n-j+1][i]);
int t = m;
m = n;
n = t;
t = r;
r = c;
c = t;
}
else
{
for ( int i = 1; i <= m; ++i )
for ( int j = 1; j <= n; ++j )
fscanf(in, "%d" , &a[i][j]);
}
}
int partition(int top, int bottom, int arr[max])
{
int x = arr[top];
int i = top - 1;
int j = bottom + 1;
int temp;
do
{
do
{
--j;
} while ( x < arr[j] );
do
{
++i;
} while ( x > arr[i] );
if ( i < j )
{
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
} while ( i < j );
return j;
}
void quicksort(int top, int bottom, int arr[max])
{
int middle;
if ( top < bottom )
{
middle = partition(top, bottom, arr);
quicksort(top, middle, arr);
quicksort(middle+1, bottom, arr);
}
return;
}
void suma()
{
int t = 0;
int b[max] = {0};
for ( int i = 1; i <= m; ++i )
for ( int j = 1; j <= n; ++j )
{
if ( eliminate[j] == 0 )
b[i] += a[i][j];
}
quicksort(1, m, b);
for ( int i = r+1; i <= m; ++i )
t += b[i];
if ( t > s )
s = t;
memset(eliminate, 0, sizeof(eliminate));
}
int st[max] = {0};
void back(int col)
{
for ( int i = st[col-1]+1; i <= n; ++i )
{
st[col] = i;
if ( col == c )
{
for ( int t = 1; t <= c; ++t )
eliminate[st[t]] = 1;
suma();
}
else
back(col+1);
}
}
//==================================================================================================
int main()
{
read();
// for ( int i = 1 ; i <= m; ++i )
// {
// for ( int j = 1; j <= n; ++j )
// printf("%d ", a[i][j]);
// printf("\n");
// }
// printf("\n");
// if ( m < n )
// {
// rot();
// int t = m;
// m = n;
// n = t;
//
// t = r;
// r = c;
// c = t;
// }
// for ( int i = 1 ; i <= m; ++i )
// {
// for ( int j = 1; j <= n; ++j )
// printf("%d ", a[i][j]);
// printf("\n");
// }
back(1);
fprintf(out, "%d\n", s);
return 0;
}