Pagini recente » Cod sursa (job #352003) | Cod sursa (job #145319) | Cod sursa (job #2131792) | Cod sursa (job #9386) | Cod sursa (job #1482085)
#define _CRT_SECURE_NO_DEPRECATE
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <algorithm>
#define MAXN 7300
#define DIM (1 << 13)
int N, M, R, C, A[MAXN][MAXN];
int RSum[MAXN], LSum[MAXN], maxx, Tsum, minn = 0x3f3f3f3f;
int in[MAXN], pos = DIM, len;
char buf[DIM];
bool Rhalf1;
inline bool cmp(int x, int y) { return x < y; }
inline int r_int32(){
while (buf[pos] < '0' || buf[pos] > '9'){
if (++pos >= DIM) len = fread(buf, 1, DIM, stdin), pos = 0;
}
int val = 0;
while (buf[pos] >= '0' && buf[pos] <= '9'){
if (pos == len) break;
val = val * 10 + buf[pos] - '0';
if (++pos == DIM) len = fread(buf, 1, DIM, stdin), pos = 0;
}
return val;
}
inline void w_int32(int k){
char lim[16], *s;
s = lim + 15, *s = 0;
do{
*--s = k % 10 + '0';
k /= 10;
} while (k);
puts(s);
}
int main(){
assert(freopen("elimin.in", "r", stdin));
freopen("elimin.out", "w", stdout);
M = r_int32(), N = r_int32(), R = r_int32(), C = r_int32();
if (M <= N){
for (int i = 0; i < M; ++i)
for (int j = 0; j < N; ++j)
A[i][j] = r_int32(),
Tsum += A[i][j],
LSum[i] += A[i][j],
RSum[j] += A[i][j];
}
else {
for (int i = 0; i < M; ++i)
for (int j = 0; j < N; ++j)
A[j][i] = r_int32(),
Tsum += A[j][i],
LSum[j] += A[j][i],
RSum[i] += A[j][i];
R ^= C ^= R ^= C;
M ^= N ^= M ^= N;
}
if (R < M >> 1) Rhalf1 = 1;
for (int i = 0; i < 1 << M; ++i){
int x = i, j = 0, sum = 0;
for (; x; x -= x & -x, ++j);
if (j != R) continue;
if (Rhalf1)
for (int j = 0; j < N; ++j) in[j] = RSum[j];
else memset(RSum, 0, sizeof(int) * N), sum = Tsum;
if (Rhalf1) {
for (int j = 0; j < M; ++j)
if (i & (1 << j)){
sum += LSum[j];
for (int k = 0; k < N; ++k) in[k] -= A[j][k];
}
}
else {
for (int j = 0; j < M; ++j)
if (!(i & (1 << j))){
sum -= LSum[j];
for (int k = 0; k < N; ++k) in[k] += A[j][k];
}
}
std::sort(in, in + N, cmp);
for (int j = 0; j < C; ++j) sum += in[j];
if (sum < minn) minn = sum;
}
w_int32(Tsum - minn);
return 0;
}