446B


  Posted on 07 Dec 2014
brute force greedy

Solution


#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

#define MAX_ROW_NUM 1005
#define MAX_COL_NUM MAX_ROW_NUM
#define D(x) 
#define MAX_K 1000005

int row_num, col_num;
int operation_num;
int decrease_value;
int matrix[MAX_ROW_NUM][MAX_COL_NUM];
int row_sum[MAX_ROW_NUM];
int col_sum[MAX_COL_NUM];
long long row_ans[MAX_K];
long long col_ans[MAX_K];

void input()
{
	scanf("%d%d", &row_num, &col_num);
	scanf("%d%d", &operation_num, &decrease_value);
	for (int i = 0; i < row_num; i++)
	{
		for (int j = 0; j < col_num; j++)
		{
			int a;
			scanf("%d", &a);
			matrix[i][j] = a;
			row_sum[i] += a;
			col_sum[j] += a;
		}
	}
}

void make(priority_queue<int> &pq, int multi)
{
	int top = pq.top();
	pq.pop();
	top -= decrease_value * multi;
	pq.push(top);
}

long long work()
{
	priority_queue<int> pq_row;
	priority_queue<int> pq_col;
	for (int i = 0; i < row_num; i++)
	{
		pq_row.push(row_sum[i]);
	}
	for (int i = 0; i < col_num; i++)
	{
		pq_col.push(col_sum[i]);
	}
	col_ans[0] = row_ans[0] = 0;
	for (int i = 1; i <= operation_num; i++)
	{
		row_ans[i] = pq_row.top() + row_ans[i - 1];
		make(pq_row, col_num);
	}
	for (int i = 1; i <= operation_num; i++)
	{
		col_ans[i] = pq_col.top() + col_ans[i - 1];
		make(pq_col, row_num);
	}
	long long ret = -(1LL << 50);
	for (int i = 0; i <= operation_num; i++)
	{
		long long temp = col_ans[i] + row_ans[operation_num - i];
		long long total_decrease = decrease_value;
		total_decrease *= i;
		total_decrease *= operation_num - i;
		temp -= total_decrease;
		ret = max(ret, temp);
	}
	return ret;
}

int main()
{
	input();
	printf("%I64d\n", work());
	return 0;
}