446B

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;
}