Cod sursa(job #1071544)

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

#define N_MAX 2000
using namespace std;

short a[N_MAX][N_MAX];
short d[20], b[20];
short m,n,r,c;

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

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

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

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

         for(int i=r;i<n;i++){
            suma+=sumalinie[i];
         }
         if(sumamax<suma)
            sumamax=suma;
       // cout<<suma<<endl;
         suma=0;
         //cout<<scade[l];
         //l++;
           //cout<<d[i];
           memset(scade,0,N_MAX);
           memset(sumalinie,0,N_MAX);
      //   cout<<endl;
     }
     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);
    }

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