Pagini recente » Cod sursa (job #947535) | Cod sursa (job #441419) | Cod sursa (job #901435) | Cod sursa (job #1888694) | Cod sursa (job #8830)
Cod sursa(job #8830)
#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], uz1[Pdoi], uz2[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);
if (k2==15)
{
k2=15;
}
for (j = 0; j < m; j++)
{
if (!((1<<j) & k))
{
if (j < 8 && !uz1[k1]) // intra la k1
{
for (i = 0; i < n; i++)
sp[i][0][k1] += a[j][i];
}
if (j >=8 && !uz2[k2]) // intra la k2
{
for (i = 0; i < n; i++)
sp[i][1][k2] += a[j][i];
}
}
}
uz1[k1] = 1;
uz2[k2] = 1;
}
}
long 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)
{
k2 = k >> 8;
k1 = k - (k2 << 8);
for (i = 0; i < n; i++)
{
sc[i] = 0;
/*for (j = 0; j < m; j++)
{
if (!((1<<j) & k))
{
sc[i] += a[j][i];
}
}
if (sc[i] != sp[i][0][k1] + sp[i][1][k2])
{
printf("oops ... eroare\n");
}*/
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;
}