Cod sursa(job #1014082)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 22 octombrie 2013 00:46:30
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <cstdio>
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <cstring>
#include <string>
#include <set>
#include <stack>
#define pb push_back

#define mp make_pair
#define f first
#define s second
#define ll long long

const int MAXN = 2 * 7 * 521;
const int MAXM = 20;

using namespace std;

int Col[MAXN];
int M, N, R, C;
int total_sum;
int ord[MAXN];
int ans;
int A[MAXM][MAXN], rem[MAXN];
int t;
inline bool cmp(const int& a, const int& b){ 
    return Col[a] < Col[b];
}
void back(int k) {
    if (k > R) {
        int _s = 0;
        
        nth_element(ord, ord + C, ord + N, cmp);

        for (int j = 0; j < N; ++j) 
            _s += Col[j];
            
        
        for (int j = 0; j < C; ++j) { 
            _s -= Col[ord[j]]; 
        }         
        if (ans < _s) 
            ans = _s;
        
    } else {
        for (int i = rem[k - 1] + 1; i <= M; ++i) {
            rem[k] = i;

            for (int j = 0; j < N; ++j) {
                Col[j] -= A[rem[k] - 1][j];
            }
            back(k + 1);
            
            for (int j = 0; j < N; ++j) {
                Col[j] += A[rem[k] - 1][j];
            }

        }
    }
}       
int main() {
    ifstream cin("elimin.in");
    ofstream cout("elimin.out");
    
    cin >> M >> N >> R >> C;

    
    //back pe linii

    if (M < N) {
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                 cin >> A[i][j];
            }
        }
    } else {
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                cin >> A[j][i] ;
            }
        }
        swap(M, N); 
        swap(R, C);
    }
    
    
    for (int j = 0; j < N; ++j)
       ord[j] = j;

    
    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < N; ++j) {
            Col[j] += A[i][j];
            total_sum += A[i][j] ;
        }
    }
    back(1);
    cout << ans << "\n";
    return 0;
}