Pagini recente » Cod sursa (job #1866942) | Cod sursa (job #2946809) | Cod sursa (job #1577201) | Cod sursa (job #350263) | Cod sursa (job #10584)
Cod sursa(job #10584)
#include <stdio.h>
#include <fstream>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;
#define in "elimin.in"
#define out "elimin.out"
int maxim=-1;
vector< vector<int> > v;
vector<int> x;
vector<int> linie; // suma de pe fiecare linie
vector<int> liniecst;
vector< vector<int> > aux;
int n, m, r, c;
long long t=0;
long long ok,ok2;
int Ok(int);
void Write(int);
void Back(int);
void ReadData();
void Qsort(int,int);
int main()
{
ReadData();
return 0;
}
void ReadData()
{
freopen(in,"r",stdin);
freopen(out,"w",stdout);
scanf("%d%d%d%d",&m,&n,&r,&c);
v.resize(m+1);
x.resize(n+1);
linie.resize(m+1);
liniecst.resize(m+1);
aux.resize(m+1);
for ( int i = 1; i <= m; i++ )
{
v[i].resize(n+1);
aux[i].resize(n+1);
}
for ( int i = 1; i <= m; i++ )
{
linie[i] = 0;
liniecst[i] = 0;
for ( int j = 1; j <= n; j++ )
{
scanf("%d",&v[i][j]);
linie[i] += v[i][j];
liniecst[i] += v[i][j];
aux[i][j] = v[i][j];
}
}
ok = 1;
ok2 = 1;
x[0] = 0;
if ( m < n )
{
aux.resize(n+1);
linie.resize(n+1);
liniecst.resize(n+1);
for ( int i = 1; i <= n; i++ )
aux[i].resize(m+1);
for ( int i = 1; i <= n; i++ )
{
linie[i] = 0;
liniecst[i] = 0;
for ( int j = 1; j <= m; j++ )
{
aux[i][j] = v[j][i];
linie[i] += v[j][i];
liniecst[i] += v[j][i];
}
}
int q = n;
n = m;
m = q;
q = r;
r = c;
c = q;
}
if ( c == 0 && r == 0 )
{
maxim = 0;
for ( int i = 1; i <= m; i++ )
maxim += linie[i];
printf("%d",maxim);
exit(0);
}
else if ( c == 0 )
{
maxim = 0;
sort(linie.begin(),linie.end() );
// Qsort(1,n);
for ( int i = r+1; i <= m; i++ )
{
maxim += linie[i];
}
printf("%d",maxim);
exit(0);
}
if ( r == 0 ) r -= 1;
Back(1);
printf("%d",maxim);
}
void Back(int k)
{
for ( int i = x[k-1]+1; i <= n; i++ )
{
x[k] = i;
// if ( Ok(k) )
{
if ( k == c ) Write(k);
else if ( k < c ) Back(k+1);
}
}
}
int Ok(int k)
{
for ( int i = 1; i < k; i++ )
if ( x[i] == x[k] ) return 0;
return 1;
}
void Write(int k)
{
int sum=0;
t+=1;
/* for ( int i = 1; i <= m; i++ )
{
linie[i] = 0;
for ( int j = 1; j <= n; j++ )
linie[i] += v[i][j];
}*/
/* for ( int j = 1; j <= k; j++ )
printf("%d ", x[j]);
printf("\n");
/* for ( int i = 1; i <= m; i++ )
for ( int j = 1; j <= k; j++ )
{
linie[i] -= v[i][x[j]];
}*/
for ( int i = 1; i <= m; i++ )
{
linie[i] = liniecst[i];
for ( int j = 1; j <= k; j++ )
{
linie[i] -= aux[i][x[j]];
}
}
sort(linie.begin(),linie.end() );
// Qsort(1,n);
for ( int i = r+1; i <= m; i++ )
{
// printf("%d ",linie[i]);
sum += linie[i];
}
// printf("\n");
if ( sum > maxim ) maxim = sum;
// if ( t == ok+2 ) printf("%lld", maxim), exit(0);
}