Pagini recente » Cod sursa (job #156571) | Cod sursa (job #252382) | Cod sursa (job #203775) | Cod sursa (job #1551773) | Cod sursa (job #1002990)
#include <fstream>
#include <algorithm>
#include <vector>
#include <limits.h>
#define IN "elimin.in"
#define OUT "elimin.out"
using namespace std;
ifstream in(IN);
ofstream out(OUT);
int r, c, sol[7300], sc[7300], sl[7300], sc2[7300], soll, n, m;
int a[500][500];
long long sumtot, mx=-2147000000;
inline void read()
{
in>>n>>m>>r>>c;
int i, j;
if(n<=m)
for(i=1; i<=n; ++i)
for(j=1; j<=m; ++j)
in>>a[i][j];
else
{
for(i=1; i<=n; ++i)
for(j=1; j<=m; ++j)
in>>a[j][i];
swap(n,m);
swap(r,c);
}
for(i=1; i<=n; ++i)
for(j=1; j<=m; ++j)
{
sl[i]+=a[i][j];
sc[j]+=a[i][j];
sumtot+=a[i][j];
}
}
inline void solution()
{
int i, j;
soll=sumtot;
for(i=1; i<=m; ++i)
sc2[i]=sc[i];
for(i=1; i<=r; ++i)
{
for(j=1; j<=m; ++j)
sc2[j]-=a[sol[i]][j];
soll-=sl[sol[i]];
}
if(c)
{
nth_element(sc2+1,sc2+c,sc2+m+1);
for(i=1; i<=c; ++i)
soll-=sc2[i];
}
if(soll>mx)
mx=soll;
}
inline void write(int lim)
{
for(int i=1; i<=lim; ++i)
out<<sol[i]<<' ';
out<<'\n';
}
inline void BT(int k)
{
if(k==r+1)
{
solution();
}
else
{
sol[k]=sol[k-1];
while(sol[k]<n)
{
++sol[k];
BT(k+1);
}
}
}
int main()
{
read();
BT(1);
out<<mx;
in.close();
out.close();
return 0;
}