Cod sursa(job #1013905)

Utilizator razvan9310FMI - Razvan Damachi razvan9310 Data 21 octombrie 2013 21:32:10
Problema Elimin Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.26 kb

#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <algorithm>
using namespace std;

template <class T> class ArrayPair {
  int index_;
  T value_;

  public:
    ArrayPair(const T &value = 0, const int &index = 0) {
      value_ = value;
      index_ = index;
    }
    bool operator <(const ArrayPair<T> &to_compare) const {
      return value_ < to_compare.value_;
    }
    int getIndex() {
      return index_;
    }
    T getValue() {
      return value_;
    }
};

vector<vector<int> > mat;
vector<ArrayPair<int> > linii, coloane;
int M, N, R, C, total;
bitset<8000> to_remove;

void input() {
  ifstream in("elimin.in");
  in>>M>>N>>R>>C;
  int i, j, val;
  for (i = 0; i < M; ++i) {
    vector<int> linie(N, 0);
    mat.push_back(linie);
    int sum = 0;
    for (j = 0; j < N; ++j) {
      in>>val;
      sum += val;
      mat[i][j] = val;
    }
    total += sum;
    //ArrayPair<int> ap(sum, i);
    //linii.push_back(ap);
  }
  in.close();
}

void solve() {
  int i, j;
  for (j = 0; j < N; ++j) {
    int sum = 0;
    for (i = 0; i < M; ++i) {
      sum += mat[i][j];
    }
    ArrayPair<int> ap(sum, j);
    coloane.push_back(ap);
  }

  sort(coloane.begin(), coloane.end());
  for (i = 0; i < C; ++i) {
    to_remove[coloane[i].getIndex()] = 1;
    total -= coloane[i].getValue();
  }

  for (i = 0; i < M; ++i) {
    int sum = 0;
    for (j = 0; j < N; ++j) {
      if (to_remove[j] == 0) {
        sum += mat[i][j];
      }
    }
    ArrayPair<int> ap(sum, i);
    linii.push_back(ap);
  }

  sort(linii.begin(), linii.end());
  for (i = 0; i < R; ++i) {
    total -= linii[i].getValue();
  }
  /*int i, j;
  sort(linii.begin(), linii.end());
  for (i = 0; i < R; ++i) {
    to_remove[linii[i].getIndex()] = 1;
    total -= linii[i].getValue();
  }

  //facem suma pe coloane:
  for (j = 0; j < N; ++j) {
    int sum = 0;
    for (i = 0; i < M; ++i) {
      if (to_remove[i] == 0) {
        sum += mat[i][j];
      }
    }
    ArrayPair<int> ap(sum, j);
    coloane.push_back(ap);
  }

  //sortam si eliminam:
  sort(coloane.begin(), coloane.end());
  for (i = 0; i < C; ++i) {
    total -= coloane[i].getValue();
  }*/
}

void output() {
  ofstream out("elimin.out");
  out<<total;
  out.close();
}

int main() {
  input();
  solve();
  output();
  return 0;
}