Pagini recente » Cod sursa (job #1781230) | Cod sursa (job #2600147) | Cod sursa (job #887218) | Cod sursa (job #2160531) | Cod sursa (job #2235833)
#include <cstdio>
#include <algorithm>
#define max(a, b) (a>b?a:b)
#define min(a, b) (a<b?a:b)
using namespace std;
int M, N, Table[1001][1001], R, C, i, j, Total, P, Q, List[1001], aux, Smax;
void Find(int Sum){
int j;
if(P==R) for(j=1; j<=Q; j++)List[j]=Table[0][j];
else for(j=1; j<=Q; j++)List[j]=Table[j][0];
sort(List+1, List+Q+1);
for(j=1; j<=N; j++)Sum-=List[j];
if(Sum>Smax)Smax=Sum;
return;
}
void BKT(int i, int last, int S){
if(i==M){Find(S); return;}
int j, k;
for(j=last+1; j<=P; j++){
for(k=1; k<=Q; k++){
if(P==R) Table[0][k]-=Table[j][k];
else Table[k][0]-=Table[k][j];
}
if(P==R)BKT(i+1, j, S-Table[j][0]);
else BKT(i+1, j, S-Table[0][j]);
for(k=1; k<=Q; k++){
if(P==R) Table[0][k]+=Table[j][k];
else Table[k][0]+=Table[k][j];
}
}
return;
}
int main()
{
freopen("elimin.in", "r", stdin);
freopen("elimin.out", "w", stdout);
scanf("%d%d%d%d", &M, &N, &R, &C);
for(i=1; i<=M; i++)
for(j=1; j<=N; j++){
scanf("%d", &Table[i][j]);
Table[i][0]+=Table[i][j];
Table[0][j]+=Table[i][j];
Total+=Table[i][j];
}
if(R==0 && C==0){printf("%d", Total); return 0;}
P=min(M, N);
Q=max(M, N);
if(P==N){aux=M; M=R; R=aux; aux=N; N=C; C=aux;}
else {aux=M; M=C; C=aux; aux=N; N=R; R=aux;}
BKT(0, 0, Total);
printf("%d", Smax);
return 0;
}