Cod sursa(job #2247455)

Utilizator pofianFilipp pofian Data 28 septembrie 2018 17:36:17
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin ("elimin.in");
ofstream fout("elimin.out");
int a[25][8205],sol,sumcol[8205],n,m,r,c,coppy[32001];
bool sel[22],invarte;

void ch(int &q1,int &q2)
{
    int aux=q1;
    q1=q2;
    q2=aux;
}

void backt(int k,int q)
{
    int i,j,sum=0;
    if(k>r)
    {
        for(j=1;j<=m;j++)
            coppy[j]=sumcol[j];
        sort(coppy+1,coppy+m+1);
        for(j=c+1;j<=m;j++)
            sum+=coppy[j];
        sol=max(sum,sol);
    }
    else
    for(i=q+1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
            sumcol[j]-=a[i][j];
        backt(k+1,i);
        for(j=1;j<=m;j++)
            sumcol[j]+=a[i][j];
    }
}

int main()
{
    int i,j;
    fin>>n>>m>>r>>c;
    if(m<n)
        invarte=1;
    for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
        if(invarte)
            fin>>a[j][i];
        else
            fin>>a[i][j];
    if(invarte)
    {
        ch(n,m);
        ch(r,c);
    }
    for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
        sumcol[j]+=a[i][j];
    backt(1,0);
    fout<<sol;
}