Cod sursa(job #2235835)

Utilizator MoldooooooooMoldoveanu Stefan Moldoooooooo Data 27 august 2018 00:06:01
Problema Elimin Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#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, X, Y;
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==X) Table[0][k]-=Table[j][k];
            else Table[k][0]-=Table[k][j];
        }
        if(P==X)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==X) 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);
    X=M; Y=N;
    if(P==M){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;
}