DZY Loves Modification (Codeforces 446B)
Tags: Greedy, data structures

As we know, DZY loves playing games. One day DZY decided to play with a n × m matrix. To be more precise, he decided to modify the matrix with exactly k operations.Each modification is one of the following:  Pick some row of the matrix and decrease each element of the row by p. This operation brings to DZY the value of pleasure equal to the sum of elements of the row before the decreasing.  Pick some column of the matrix and decrease each element of the column by p. This operation brings to DZY the value of pleasure equal to the sum of elements of the column before the decreasing. DZY wants to know: what is the largest total value of pleasure he could get after performing exactly k modifications? Please, help him to calculate this value.

Input: The first line contains four space-separated integers n, m, k and p (1 ≤ n, m ≤ 103; 1 ≤ k ≤ 106; 1 ≤ p ≤ 100).Then n lines follow. Each of them contains m integers representing aij (1 ≤ aij ≤ 103) — the elements of the current row of the matrix.

Output: Output a single integer — the maximum possible total pleasure value DZY could get.

Note: For the first sample test, we can modify: column 2, row 2. After that the matrix becomes:1 10 0For the second sample test, we can modify: column 2, row 2, row 1, column 1, column 2. After that the matrix becomes:-3 -3-2 -2

Sample Inputs:
2 2 2 2
1 3
2 4

2 2 5 2
1 3
2 4

Sample Outputs:
11

11

Solution (Python):
import heapq

def main():
    (n, m, k, p) = map(int, input().split())
    h = []
    g = []
    (row_v, col_v) = ([0], [0])
    for _ in range(n):
        row = list(map(int, input().split()))
        heapq.heappush(h, -sum(row))
        g.append(row)
    for i in range(1, k + 1):
        value = heapq.heappop(h)
        row_v.append(row_v[-1] - value)
        heapq.heappush(h, value + p * m)
    h = []
    for s in zip(*g):
        heapq.heappush(h, -sum(s))
    for j in range(1, k + 1):
        value = heapq.heappop(h)
        col_v.append(col_v[-1] - value)
        heapq.heappush(h, value + p * n)
    ans = float('-inf')
    for i in range(k + 1):
        ans = max(ans, row_v[i] + col_v[k - i] - p * i * (k - i))
    print(ans)
    return
main()

Solution (Python):
import sys
input = sys.stdin.buffer.readline
(n, m, k, p) = map(int, input().split())
a = [list(map(int, input().split())) for i in range(n)]

def compute_best(b, n, m):
    mn = min(b)
    count = [0] * (10 ** 6 + 10 ** 5)
    for i in b:
        count[i] += 1
    count_i = 10 ** 6
    curr_op = 1
    best = [0] * (k + 1)
    while curr_op <= k:
        while not count[count_i]:
            count_i -= 1
        best[curr_op] = count_i + best[curr_op - 1]
        curr_op += 1
        count[count_i] -= 1
        new = count_i - p * n
        count[new] += 1
        if new <= mn:
            break
    for i in range(m):
        while not count[count_i]:
            count_i -= 1
        b[i] = count_i
        count[count_i] -= 1
    left = k - curr_op + 1
    for i in range(left):
        best[curr_op + i] = best[curr_op + i - 1] + b[i % m] - i // m * p * n
    return best
best_rows = compute_best([sum(a[i]) for i in range(n)], m, n)
best_cols = compute_best([sum([a[i][j] for i in range(n)]) for j in range(m)], n, m)
ans = -1e+18
for i in range(k + 1):
    ans = max(ans, best_rows[i] + best_cols[k - i] - i * p * (k - i))
print(ans)

Solution (Python):
""""""
import os
import sys
from io import BytesIO, IOBase
import heapq as h
import bisect
from types import GeneratorType
BUFSIZE = 8192

class SortedList:

    def __init__(self, iterable=[], _load=200):
        """"""
        values = sorted(iterable)
        self._len = _len = len(values)
        self._load = _load
        self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
        self._list_lens = [len(_list) for _list in _lists]
        self._mins = [_list[0] for _list in _lists]
        self._fen_tree = []
        self._rebuild = True

    def _fen_build(self):
        """"""
        self._fen_tree[:] = self._list_lens
        _fen_tree = self._fen_tree
        for i in range(len(_fen_tree)):
            if i | i + 1 < len(_fen_tree):
                _fen_tree[i | i + 1] += _fen_tree[i]
        self._rebuild = False

    def _fen_update(self, index, value):
        """"""
        if not self._rebuild:
            _fen_tree = self._fen_tree
            while index < len(_fen_tree):
                _fen_tree[index] += value
                index |= index + 1

    def _fen_query(self, end):
        """"""
        if self._rebuild:
            self._fen_build()
        _fen_tree = self._fen_tree
        x = 0
        while end:
            x += _fen_tree[end - 1]
            end &= end - 1
        return x

    def _fen_findkth(self, k):
        """"""
        _list_lens = self._list_lens
        if k < _list_lens[0]:
            return (0, k)
        if k >= self._len - _list_lens[-1]:
            return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
        if self._rebuild:
            self._fen_build()
        _fen_tree = self._fen_tree
        idx = -1
        for d in reversed(range(len(_fen_tree).bit_length())):
            right_idx = idx + (1 << d)
            if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
                idx = right_idx
                k -= _fen_tree[idx]
        return (idx + 1, k)

    def _delete(self, pos, idx):
        """"""
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens
        self._len -= 1
        self._fen_update(pos, -1)
        del _lists[pos][idx]
        _list_lens[pos] -= 1
        if _list_lens[pos]:
            _mins[pos] = _lists[pos][0]
        else:
            del _lists[pos]
            del _list_lens[pos]
            del _mins[pos]
            self._rebuild = True

    def _loc_left(self, value):
        """"""
        if not self._len:
            return (0, 0)
        _lists = self._lists
        _mins = self._mins
        (lo, pos) = (-1, len(_lists) - 1)
        while lo + 1 < pos:
            mi = lo + pos >> 1
            if value <= _mins[mi]:
                pos = mi
            else:
                lo = mi
        if pos and value <= _lists[pos - 1][-1]:
            pos -= 1
        _list = _lists[pos]
        (lo, idx) = (-1, len(_list))
        while lo + 1 < idx:
            mi = lo + idx >> 1
            if value <= _list[mi]:
                idx = mi
            else:
                lo = mi
        return (pos, idx)

    def _loc_right(self, value):
        """"""
        if not self._len:
            return (0, 0)
        _lists = self._lists
        _mins = self._mins
        (pos, hi) = (0, len(_lists))
        while pos + 1 < hi:
            mi = pos + hi >> 1
            if value < _mins[mi]:
                hi = mi
            else:
                pos = mi
        _list = _lists[pos]
        (lo, idx) = (-1, len(_list))
        while lo + 1 < idx:
            mi = lo + idx >> 1
            if value < _list[mi]:
                idx = mi
            else:
                lo = mi
        return (pos, idx)

    def add(self, value):
        """"""
        _load = self._load
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens
        self._len += 1
        if _lists:
            (pos, idx) = self._loc_right(value)
            self._fen_update(pos, 1)
            _list = _lists[pos]
            _list.insert(idx, value)
            _list_lens[pos] += 1
            _mins[pos] = _list[0]
            if _load + _load < len(_list):
                _lists.insert(pos + 1, _list[_load:])
                _list_lens.insert(pos + 1, len(_list) - _load)
                _mins.insert(pos + 1, _list[_load])
                _list_lens[pos] = _load
                del _list[_load:]
                self._rebuild = True
        else:
            _lists.append([value])
            _mins.append(value)
            _list_lens.append(1)
            self._rebuild = True

    def discard(self, value):
        """"""
        _lists = self._lists
        if _lists:
            (pos, idx) = self._loc_right(value)
            if idx and _lists[pos][idx - 1] == value:
                self._delete(pos, idx - 1)

    def remove(self, value):
        """"""
        _len = self._len
        self.discard(value)
        if _len == self._len:
            raise ValueError('{0!r} not in list'.format(value))

    def pop(self, index=-1):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        value = self._lists[pos][idx]
        self._delete(pos, idx)
        return value

    def bisect_left(self, value):
        """"""
        (pos, idx) = self._loc_left(value)
        return self._fen_query(pos) + idx

    def bisect_right(self, value):
        """"""
        (pos, idx) = self._loc_right(value)
        return self._fen_query(pos) + idx

    def count(self, value):
        """"""
        return self.bisect_right(value) - self.bisect_left(value)

    def __len__(self):
        """"""
        return self._len

    def __getitem__(self, index):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        return self._lists[pos][idx]

    def __delitem__(self, index):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        self._delete(pos, idx)

    def __contains__(self, value):
        """"""
        _lists = self._lists
        if _lists:
            (pos, idx) = self._loc_left(value)
            return idx < len(_lists[pos]) and _lists[pos][idx] == value
        return False

    def __iter__(self):
        """"""
        return (value for _list in self._lists for value in _list)

    def __reversed__(self):
        """"""
        return (value for _list in reversed(self._lists) for value in reversed(_list))

    def __repr__(self):
        """"""
        return 'SortedList({0})'.format(list(self))

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        import os
        self.os = os
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            self.os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import collections as col
import math, string

def getInts():
    return [int(s) for s in input().split()]

def getInt():
    return int(input())

def getStrs():
    return [s for s in input().split()]

def getStr():
    return input()

def listStr():
    return list(input())
MOD = 10 ** 9 + 7
mod = 10 ** 9 + 7
t = 1
p = 10 ** 9 + 7

def ncr_util():
    inv[0] = inv[1] = 1
    fact[0] = fact[1] = 1
    for i in range(2, 300001):
        inv[i] = inv[i % p] * (p - p // i) % p
    for i in range(1, 300001):
        inv[i] = inv[i - 1] * inv[i] % p
        fact[i] = fact[i - 1] * i % p

def solve():
    l1 = []
    l2 = []
    h.heapify(l1)
    h.heapify(l2)
    for i in range(n):
        suma = 0
        for j in range(m):
            suma += l[i][j]
        h.heappush(l1, -1 * suma)
    for j in range(m):
        suma = 0
        for i in range(n):
            suma += l[i][j]
        h.heappush(l2, -1 * suma)
    ans = 0
    (row, col) = (0, 0)
    r1 = [0] * (k + 1)
    c1 = [0] * (k + 1)
    for _ in range(k):
        (x1, x2) = (-h.heappop(l1), -h.heappop(l2))
        r1[_ + 1] = r1[_] + x1
        c1[_ + 1] = c1[_] + x2
        x1 -= m * p
        x2 -= n * p
        h.heappush(l1, -x1)
        h.heappush(l2, -x2)
    ans = r1[k]
    for i in range(k + 1):
        ans = max(ans, r1[i] + c1[k - i] - i * (k - i) * p)
    return ans
for _ in range(t):
    (n, m, k, p) = map(int, input().split())
    l = []
    for i in range(n):
        l.append(list(map(int, input().split())))
    print(solve())