Cod sursa(job #2450164)

Utilizator CharacterMeCharacter Me CharacterMe Data 22 august 2019 10:41:19
Problema Elimin Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <bits/stdc++.h>
///N*M=7294
using namespace std;
///
int n, m, r, c, i, j, k, sum, out;
int val[530][530], sumcol[530], sumline[530], container[530], last[530];
///
void read();
void solve();
void write();
void bkt(int i);
int main()
{
    read();
    solve();
    write();
    return 0;
}
void read(){
    freopen("elimin.in", "r", stdin);
    scanf("%d%d%d%d", &n, &m, &r, &c);
    for(i=1; i<=n; ++i)
    for(j=1; j<=m; ++j) {
        scanf("%d", &val[i][j]);
        sum+=val[i][j];
    }
    fclose(stdin);
}
void solve(){
    if(n>m){
        swap(r, c);
        for(i=1; i<=n; ++i)
        for(j=1; j<i; ++j) swap(val[i][j], val[j][i]);
        swap(n, m);
    }
    for(i=1; i<=n; ++i){
        for(j=1; j<=m; ++j) {
            sumline[i]+=val[i][j];
            sumcol[j]+=val[i][j];
        }
    }
    bkt(0);
}
void write(){
    freopen("elimin.out", "w", stdout);
    printf("%d", out);
    fclose(stdout);
}
void bkt(int i){
    if(i==r){
        for(int j=1; j<=m; ++j) container[j]=sumcol[j];
        sort(container+1, container+m+1);
        int s=0;
        for(int j=m; j>=c+1; --j) s+=container[j];
        out=max(out, s);
        return;
    }
    for(int j=last[i]+1; j<=n; ++j){
        for(int k=1; k<=m; ++k) sumcol[k]-=val[j][k];
        last[i+1]=j;
        bkt(i+1);
        for(int k=1; k<=m; ++k) sumcol[k]+=val[j][k];
    }
}