Cod sursa(job #1014031)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 21 octombrie 2013 23:28:41
Problema Elimin Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.99 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 = 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[MAXN][MAXM], rem[MAXN];

inline bool cmp(const int& a, const int& b){ 
    return Col[a] < Col[b];
}
void back(int k) {
    if (k == R) {

        int tmp = total_sum;
         
        nth_element(ord, ord + C, ord + N, cmp);
         
        for (int j = 0; j < C; ++j) {
            tmp -= Col[ord[j]];
        //    cerr << Col[ord[j]] << " " ;    
        }
        if (ans < tmp) {
            ans = tmp;
        }
    } else {
        for (int i = rem[k - 1] + 1; i <= M; ++i) {
            rem[k] = i;
            
            for (int j = 0; j < N; ++j) {
                Col[j] -= A[i - 1][j];
                total_sum -= A[i - 1][j];
            }

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

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

    for (int i = 0; i < N; ++i)
        ord[i] = i;
    //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 i = 0; i < M; ++i) {
        for (int j = 0; j < N; ++j) {
            Col[j] += A[i][j]; total_sum += A[i][j];
        }
    }

    back(0);
    cout << ans << "\n";
    return 0;
}