C. Strange Game On Matrix

Codeforces

IDCF873C

Time1000ms

Memory256MB

Difficulty—

greedytwo pointers

English · Original

Chinese · Translation

Formal · Original

Ivan is playing a strange game. He has a matrix _a_ with _n_ rows and _m_ columns. Each element of the matrix is equal to either 0 or 1. Rows and columns are 1\-indexed. Ivan can replace any number of ones in this matrix with zeroes. After that, his score in the game will be calculated as follows: 1. Initially Ivan's score is 0; 2. In each column, Ivan will find the topmost 1 (that is, if the current column is _j_, then he will find minimum _i_ such that _a__i_, _j_ = 1). If there are no 1's in the column, this column is skipped; 3. Ivan will look at the next _min_(_k_, _n_ - _i_ + 1) elements in this column (starting from the element he found) and count the number of 1's among these elements. This number will be added to his score. Of course, Ivan wants to maximize his score in this strange game. Also he doesn't want to change many elements, so he will replace the minimum possible number of ones with zeroes. Help him to determine the maximum possible score he can get and the minimum possible number of replacements required to achieve that score. ## Input The first line contains three integer numbers _n_, _m_ and _k_ (1 ≤ _k_ ≤ _n_ ≤ 100, 1 ≤ _m_ ≤ 100). Then _n_ lines follow, _i_\-th of them contains _m_ integer numbers — the elements of _i_\-th row of matrix _a_. Each number is either 0 or 1. ## Output Print two numbers: the maximum possible score Ivan can get and the minimum number of replacements required to get this score. [samples] ## Note In the first example Ivan will replace the element _a_1, 2.

Ivan 正在玩一个奇怪的游戏。他有一个包含 #cf_span[n] 行和 #cf_span[m] 列的矩阵 #cf_span[a]。矩阵的每个元素均为 #cf_span[0] 或 #cf_span[1]。行和列均为 #cf_span[1]-索引。Ivan 可以将矩阵中的任意数量的 1 替换为 0。之后，他的游戏得分将按如下方式计算：显然，Ivan 希望最大化他的得分。同时，他不想更改太多元素，因此他会替换尽可能少的 1 为 0。请帮助他确定他能得到的最大可能得分，以及达到该得分所需的最少替换次数。第一行包含三个整数 #cf_span[n]、#cf_span[m] 和 #cf_span[k]（#cf_span[1 ≤ k ≤ n ≤ 100]，#cf_span[1 ≤ m ≤ 100]）。接下来 #cf_span[n] 行，第 #cf_span[i] 行包含 #cf_span[m] 个整数——矩阵 #cf_span[a] 的第 #cf_span[i] 行的元素。每个数均为 #cf_span[0] 或 #cf_span[1]。请输出两个数：Ivan 能获得的最大可能得分，以及达到该得分所需的最少替换次数。在第一个例子中，Ivan 将替换元素 #cf_span[a1, 2]。 ## Input 第一行包含三个整数 #cf_span[n]、#cf_span[m] 和 #cf_span[k]（#cf_span[1 ≤ k ≤ n ≤ 100]，#cf_span[1 ≤ m ≤ 100]）。接下来 #cf_span[n] 行，第 #cf_span[i] 行包含 #cf_span[m] 个整数——矩阵 #cf_span[a] 的第 #cf_span[i] 行的元素。每个数均为 #cf_span[0] 或 #cf_span[1]。 ## Output 请输出两个数：Ivan 能获得的最大可能得分，以及达到该得分所需的最少替换次数。 [samples] ## Note 在第一个例子中，Ivan 将替换元素 #cf_span[a1, 2]。

**Definitions** Let $ n, m, k \in \mathbb{Z}^+ $ with $ 1 \leq k \leq n \leq 100 $, $ 1 \leq m \leq 100 $. Let $ A = (a_{i,j}) \in \{0,1\}^{n \times m} $ be the given binary matrix. Let $ R \subseteq \{1, \dots, n\} $ be a set of exactly $ k $ rows selected to contribute to the score. Let $ S(R) = \sum_{j=1}^m \max_{i \in R} a_{i,j} $ be the score for row set $ R $. Let $ C(R) = \sum_{i \in R} \sum_{j=1}^m (1 - a_{i,j}) $ be the number of replacements needed to turn all $ 0 $s in rows $ R $ to $ 1 $s (so that the max per column is achieved). Let $ T(R) = \sum_{i \notin R} \sum_{j=1}^m a_{i,j} $ be the number of $ 1 $s outside $ R $ that must be replaced with $ 0 $s. **Constraints** 1. $ |R| = k $ 2. Only $ 1 \to 0 $ replacements are allowed. **Objective** Maximize $ S(R) $, and among all $ R $ achieving maximum $ S(R) $, minimize total replacements: $$ \text{Minimize } C(R) + T(R) $$

Samples

Input #1

Output #1

4 1

Input #2

Output #2

2 0

API Response (JSON)

{
  "problem": {
    "name": "C. Strange Game On Matrix",
    "description": {
      "content": "Ivan is playing a strange game. He has a matrix _a_ with _n_ rows and _m_ columns. Each element of the matrix is equal to either 0 or 1. Rows and columns are 1\\-indexed. Ivan can replace any number o",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF873C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Ivan is playing a strange game.\n\nHe has a matrix _a_ with _n_ rows and _m_ columns. Each element of the matrix is equal to either 0 or 1. Rows and columns are 1\\-indexed. Ivan can replace any number o...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Ivan 正在玩一个奇怪的游戏。\n\n他有一个包含 #cf_span[n] 行和 #cf_span[m] 列的矩阵 #cf_span[a]。矩阵的每个元素均为 #cf_span[0] 或 #cf_span[1]。行和列均为 #cf_span[1]-索引。Ivan 可以将矩阵中的任意数量的 1 替换为 0。之后，他的游戏得分将按如下方式计算：\n\n显然，Ivan 希望最大化他的得分。同时，他不想更改太多...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m, k \\in \\mathbb{Z}^+ $ with $ 1 \\leq k \\leq n \\leq 100 $, $ 1 \\leq m \\leq 100 $.  \nLet $ A = (a_{i,j}) \\in \\{0,1\\}^{n \\times m} $ be the given binary matrix.  \n\nLet $ R \\su...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments