Pagini recente » Cod sursa (job #1052259) | Cod sursa (job #2742633) | Cod sursa (job #1666002) | Cod sursa (job #2095672) | Cod sursa (job #8802)
Cod sursa(job #8802)
#include <stdio.h>
#include <stdlib.h>
#define NMin 16
#define NMax 7295
#define Pdoi 257
FILE *fin, *fout;
long n, m, r, c, a[NMin][NMax];
long sl[NMax], sc[NMax], maxt;
long sp[NMax][2][Pdoi], uz[Pdoi];
void citire()
{
long i, j;
fin = fopen("elimin.in", "rt");
fscanf(fin, "%ld %ld %ld %ld", &m, &n, &r, &c);
if (m > n)
{
for (i = 0; i < m; i++)
for (j = 0; j < n; j++)
fscanf(fin, "%ld", & a[j][i]);
i = m; m = n; n = i;
i = r; r = c; c = i;
}
else
{
for (i = 0; i < m; i++)
for (j = 0; j < n; j++)
fscanf(fin, "%ld", & a[i][j]);
}
fclose(fin);
}
void preprocesare()
{
long i, j, k, k1, k2;
for (k = 0; k < 1<<m; k++)
{
// k = 0 0 0 0 0 0 0 0 0 0
// ********* ---------
// k2 k1
k2 = k >> 8;
k1 = k - (k2 << 8);
for (j = 0; j < m; j++)
{
if (!((1<<j) & k))
{
if (j < 8 && !uz[k1]) // intra la k1
{
for (i = 0; i < n; i++)
sp[i][0][k1] += a[j][i];
}
else if (!uz[k2]) // intra la k2
{
for (i = 0; i < n; i++)
sp[i][1][k2] += a[j][i];
}
}
}
uz[k1] = 1;
uz[k2] = 1;
}
}
int comp(const void *a, const void *b)
{
return (*(long*)a)-(*(long*)b);
}
void bkt()
{
long i, j, k, nr, k1, k2;
for (k = 0; k < 1<<m; k++) // bitii lui k reprezinta randurile pe care le scot
{
nr = 0;
for (j = 1; j < 1<<m; j*=2)
{
if (j & k) nr++;
}
if (nr == r)
{
for (i = 0; i < n; i++)
{
k2 = k >> 8;
k1 = k - (k2 << 8);
sc[i] = sp[i][0][k1] + sp[i][1][k2];
}
qsort(sc, n, sizeof(sc[0]), comp);
nr = 0;
for (i = c; i < n; i++)
nr+= sc[i];
if (nr > maxt)
maxt = nr;
}
}
}
void afisare()
{
fout = fopen("elimin.out", "wt");
fprintf(fout, "%ld\n", maxt);
fclose(fout);
}
int main()
{
citire();
preprocesare();
bkt();
afisare();
return 0;
}