Cod sursa(job #1945898)

Utilizator adystar00Bunea Andrei adystar00 Data 29 martie 2017 18:58:43
Problema Elimin Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
int n,m,r,c,maxx=0;
bool seen[8000];
int a[20][8000],d[20][8000],sum[8000];
void check()
{
    int i,j,k=0,t;
    long long suma=0;
    for(i=0; i<n; i++)
    {
        if(seen[i]==1)
            continue;
        for(j=0; j<m; j++)
            d[k][j]=a[i][j];
        k++;
    }
    for(j=0; j<m; j++)
    {
        sum[j]=0;
        for(t=0; t<k; t++)
            sum[j]+=d[t][j];
    }
    sort(sum,sum+m);
    for(j=c; j<m; j++)
        suma+=sum[j];
    if(suma>maxx)
        maxx=suma;
}
void backtracking(int niv, int poz)
{
    int i,ans;
    if(niv==r)
    {
        check();
        return;
    }
    for(i=poz; i<n; i++)
    {
        seen[i]=1;
        backtracking(poz+1,i+1);
        seen[i]=0;
    }
}
int main()
{
    ifstream fin ("elimin.in");
    ofstream fout ("elimin.out");
    int aux,i,j;
    fin>>n>>m>>r>>c;
    if(n>m)
    {
        aux=n;
        n=m;
        m=aux;
        aux=r;
        r=c;
        c=aux;
        for(i=0; i<m; i++)
            for(j=0; j<n; j++)
                fin>>a[j][i];
    }
    else
    {
        for(i=0; i<n; i++)
            for(j=0; j<m; j++)
                fin>>a[i][j];
    }
    backtracking(0,0);
    fout<<maxx;
    return 0;
}