Pagini recente » Cod sursa (job #1090524) | Cod sursa (job #191184) | Infoarena Monthly 2014 - Solutii Runda 1 | Cod sursa (job #2711414) | Cod sursa (job #461818)
Cod sursa(job #461818)
#include <stdio.h>
#include <stdlib.h>
void sort(int* array, int inc, int sf)
{
if(sf - inc <= 1)
return;
int i = inc;
int s = sf;
int poz = i;
while(i<s)
{
while(poz < s && array[poz] < array[s])
--s;
if(poz < s)
{
int t = array[s];
array[s] = array[poz];
array[poz] = t;
poz = s;
while(poz > i && array[poz] > array[i])
++i;
if(poz > i)
{
int t = array[i];
array[i] = array[poz];
array[poz] = t;
poz = i;
}
else
{
sort(array, i, poz - 1);
sort(array, poz+1, s);
return;
}
}
else
{
sort(array, i, poz - 1);
sort(array, poz+1, s);
return;
}
}
}
int main(void)
{
int m,n, r, c;
int* matrice;
int* coloane;
int* coloanes;
int* idxranduri;
long max = 0;
freopen("elimin.in", "r", stdin);
freopen("elimin.out", "w", stdout);
scanf("%d %d %d %d", &m, &n, &r, &c);
matrice = (int*)malloc(m*n*sizeof(int));
int i;
if(m<=n)
{
for(i=0;i<m;++i)
{
for(int j=0;j<n;++j)
{
scanf("%d ", matrice+n*i+j);
}
}
}
else
{
for(i=0;i<m;++i)
{
for(int j=0;j<n;++j)
{
scanf("%d ", matrice+i+m*j);
}
}
int t = m;
m = n;
n = t;
t = r;
r = c;
c = t;
}
coloane = (int*)malloc(n*sizeof(int));
coloanes = (int*)malloc(n*sizeof(int));
idxranduri = (int*)malloc((r+1)*sizeof(int));
for(i=0;i<n;++i)
coloane[i] = 0;
for(i=0;i<m;++i)
{
for(int j=0;j<n;++j)
{
coloane[j] += matrice[n*i+j];
}
}
int rand = 0;
idxranduri[0] = 0;
while(idxranduri[0] < m)
{
if(idxranduri[rand] < m)
{
++rand;
idxranduri[rand] = idxranduri[rand-1]+1;
}
else
{
--rand;
++idxranduri[rand];
}
if(rand >= r)
{
for(i=0; i<n; ++i)
coloanes[i] = coloane[i];
for(i=0;i<r;++i)
{
for(int j=0;j<n;++j)
coloanes[j] -= matrice[n*idxranduri[i]+j];
}
for(i=1;i<n;++i)
{
int a = coloanes[i];
int poz = i-1;
while(poz>=0 && coloanes[poz] > a)
{
coloanes[poz+1] = coloanes[poz];
--poz;
}
coloanes[poz+1] = a;
}
// sort(coloanes, 0, n-1);
int sum = 0;
for(i=c;i<n;++i)
sum += coloanes[i];
if(sum > max)
max = sum;
--rand;
++idxranduri[rand];
}
}
printf("%ld\n", max);
free(matrice);
free(coloane);
free(coloanes);
free(idxranduri);
return 0;
}