Pagini recente » Cod sursa (job #1201753) | Cod sursa (job #13088) | Cod sursa (job #2947489) | Cod sursa (job #3158541) | Cod sursa (job #60131)
Cod sursa(job #60131)
#include <cstdio>
//#include <iostream>
#include <algorithm>
using namespace std;
#define max 600
#define min 30
FILE *in = fopen("elimin.in","r"), *out = fopen("elimin.out","w");
int n, m, r, c;
short a[max][min];
//short **a;
int eliminate[max] = {0};
int s = 0;
void read()
{
fscanf(in, "%d %d %d %d", &m, &n, &r, &c);
if ( m <= n )
{
// a = new short*[n];
// for ( int i = 1; i <= n; ++i )
// a[i] = new short[m];
for ( int i = 1; i <= m; ++i )
for ( int j = 0; j < n; ++j )
fscanf(in, "%d" , &a[n-j][i]);
n = n ^ m;
m = n ^ m;
n = n ^ m;
r = r ^ c;
c = r ^ c;
r = r ^ c;
}
else
{
// a = new short*[m];
// for ( int i = 1; i <= m; ++i )
// a[i] = new short[n];
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[])
//{
// int x = arr[top];
// int i = top - 1;
// int j = bottom + 1;
// do
// {
// do
// {
// --j;
// } while ( x < arr[j] );
//
// do
// {
// ++i;
// } while ( x > arr[i] );
//
// if ( i < j )
// {
// arr[i] = arr[i] ^ arr[j];
// arr[j] = arr[i] ^ arr[j];
// arr[i] = arr[i] ^ arr[j];
// }
// } while ( i < j );
//
// return j;
//}
//
//void quicksort(int top, int bottom, int arr[])
//{
// 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] )
b[i] += a[i][j];
}
}
//quicksort(1, m, b);
sort(b, b+m);
for ( int i = r+1; i <= m; ++i )
t += b[i];
if ( t > s )
s = t;
//memset(eliminate, 0, sizeof(eliminate));
for ( int i = 1; i <= n; ++i )
eliminate[i] = 0;
}
short 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();
if ( c == 0 && r == 0 )
{
for ( int i = 1; i <= m; ++i )
for ( int j = 1; j <= n; ++j )
s += a[i][j];
}
else if ( c == 0 )
{
for ( int i = 1; i <= m; ++i )
for ( int j = 1; j <= n; ++j )
eliminate[i] += a[i][j];
//quicksort(1, m, eliminate);
sort(eliminate, eliminate+m);
for ( int i = r+1; i <= m; ++i )
s += eliminate[i];
}
else if ( r == 0 )
{
for ( int i = 1; i <= m; ++i )
for ( int j = 1; j <= n; ++j )
eliminate[j] += a[j][i];
//quicksort(1, n, eliminate);
sort(eliminate, eliminate+n);
for ( int i = c+1; i <= n; ++i )
s += eliminate[i];
}
else
back(1);
fprintf(out, "%d\n", s);
return 0;
}