Cod sursa(job #2680836)

Utilizator teochess2017Togan Teodor-Bogdan teochess2017 Data 4 decembrie 2020 14:40:19
Problema Elimin Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <stdio.h>/// am inversat n cu m din greseala
#include <vector>

using namespace std;

#define MAXARIE 7294
#define MAXEL 32000

vector <int> mat[MAXARIE];
vector <int> v;
vector <int> sl;
int frecv[7294];

int mins = MAXEL * MAXARIE + 1, n, m, r, c;

void quickselect(int mi, int ma, int poz){
  int b, e, piv, aux;
  b = mi;
  e = ma;
  piv = v[(mi + ma) / 2];
  while(piv > v[b]){
    b++;
  }
  while(piv < v[e]){
    e--;
  }
  while(b < e){
    aux = v[b];
    v[b] = v[e];
    v[e] = aux;
    do{
      b++;
    }while(piv > v[b]);
    do{
      e--;
    }while(piv < v[e]);
  }
  if((poz < e) && (mi < e)){
    quickselect(mi, e, poz);
  }else if((e + 1) < ma){
    quickselect(e + 1, ma, poz);
  }
}
void combinari(int l, int ac, int s){
  int col;
  if(ac < r){
    for(; l < (n - r + ac + 1); l++){
      frecv[l] = 1;
      combinari(l + 1, ac + 1, s + sl[l]);
      frecv[l] = 0;
    }
  }else{
    for(l = 0; l < n; l++){
      if(frecv[l] == 0){
        for(col = 0; col < m; col++){
          v[col] += mat[l][col];
        }
      }
    }
    for(col = 0; col < c; col++){
      quickselect(0, m - 1, col);
      s += v[col];
      v[col] = 0;
    }
    for(; col < m; col++){
      v[col] = 0;
    }
    if(s < mins){
      mins = s;
    }
  }
}
int main()
{
    FILE *fin, *fout;
    int l, col, el, stotal;
    fin = fopen("elimin.in", "r");
    fscanf(fin, "%d%d%d%d", &n, &m, &r, &c);
    stotal = 0;
    for(l = 0; l < n; l++){
      for(col = 0; col < m; col++){
        fscanf(fin, "%d", &el);
        stotal += el;
        mat[l].push_back(el);
        if(col == 0){
          sl.push_back(el);
        }else{
          sl[l] += el;
        }
      }
    }
    fclose(fin);
    for(col = 0; col < m; col++){
      v.push_back(0);
    }
    combinari(0, 0, 0);
    fout = fopen("elimin.out", "w");
    fprintf(fout, "%d", stotal - mins);
    fclose(fout);
    return 0;
}