Cod sursa(job #1071566)

Utilizator Aleks10FMI - Petrache Alex Aleks10 Data 3 ianuarie 2014 01:54:24
Problema Elimin Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>

using namespace std;

#define N_MAX 7000
int a[600][20];
int d[600], b[600];
int m,n,r,c;

int scade[600];
int sumalinie[600];
int suma=0;
int sumamax=0;

void back(int k)
{
     if(k-1 == c) //afisam solutia
     {
                for(int j=1;j<=n;j++){
                    for(int i = 1; i <= c;i++){
                        scade[j]+=a[j][d[i]];
                }
         }

         for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                sumalinie[i]+=a[i][j];
            }
            sumalinie[i]-=scade[i];
         }

         //sort(sumalinie+0, sumalinie+n);
         nth_element(sumalinie+1,sumalinie+r+1,sumalinie+n+1);

         for(int i=r+1;i<=n;i++){
            suma+=sumalinie[i];
         }
         if(sumamax<suma)
            sumamax=suma;

         suma=0;
           memset(scade,0,N_MAX);
           memset(sumalinie,0,N_MAX);
     }
     else
     {
         for(int  i = 1; i <= m; i++)
            if(!b[i] && d[k-1] < i)  //ne asiguram ca generam solutiile crescatoare si unice
           {
                 d[k] = i;
                 b[i] = 1; //o folosim
                 back(k+1); //trecem la pasul urmator
                 b[i] = 0;   //o eliberam
           }
     }
}

int main()
{
    int i,j;
    ifstream f("elimin.in");
    ofstream g("elimin.out");
    f>>n>>m>>r>>c;
  /*  for(i=0;i<n;i++){
        for(j=0;j<m;j++){
            f>>a[i][j];
        }
    }

    if(n<m){
        for(i=0;i<n;i++){
            for(j=0;j<m;j++){
                if(j>i)
                    swap(a[i][j],a[j][i]);
            }
        }
        swap(n,m);
        swap(r,c);
    }*/

    if (m <= n) {
        for(i=1;i<=n;i++){
            for(j=1;j<=m;j++){
                f>>a[i][j];
            }
        }
    }
    else {
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
                f>>a[j][i];
        swap(m, n); swap(r, c);
    }

    back(1);
    g<<sumamax;
    return 0;
}