AT_joi2008yo_e.おせんべい

通过率:0%

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

在 IOI 制果公司,自创业以来一直采用传统工艺烤制煎饼。这一传统工艺是:先用炭火烤一定时间的正面,等正面烤好后翻面,再用炭火烤一定时间的反面。公司在遵循这一传统的同时,使用机器批量烤制煎饼。这台机器可以将煎饼按纵向 RR(1≤R≤101 \leq R \leq 10)行、横向 CC(1≤C≤100001 \leq C \leq 10000)列的矩形排列进行烤制。通常情况下,机器自动运行,正面烤好后会一次性将所有煎饼翻面,再烤反面。

某天,在煎饼正要翻面时发生了地震,导致部分煎饼被提前翻面。幸运的是,炭火状态依然合适,但如果继续烤正面,就会超过自创业以来规定的烤制时间,导致煎饼正面烤过头,无法作为商品出货。因此,必须紧急切换到手动操作,只翻转那些还未翻面的煎饼。该机器只能同时翻转若干横行或若干纵列,无法单独翻转一块煎饼。

如果翻转操作耗时过长,未被地震翻转的煎饼正面会烤过头,无法出货。因此,计划先同时翻转若干横行一次,接着再同时翻转若干纵列一次,使得能两面都烤好的煎饼(即“可出货的煎饼”)数量尽可能多。也可以选择不翻转任何横行或不翻转任何纵列。请编写程序,输出可出货煎饼的最大数量。

地震后,煎饼的状态如图所示。黑色圆点表示正面朝上,白色圆点表示反面朝上。

2008-yo-t5-1.png

若翻转第 11 行,状态如下图:

2008-yo-t5-2.png

再翻转第 11 列和第 55 列,状态如下图。在这种状态下,可出货的煎饼有 99 块。

2008-yo-t5-3.png

输入格式

输入的第 11 行包含两个整数 R, CR,\ C(1≤R≤10, 1≤C≤10 0001 \leq R \leq 10,\ 1 \leq C \leq 10\,000),用空格分隔。接下来的 RR 行表示地震后煎饼的状态。第 i+1i+1 行(1≤i≤R1 \leq i \leq R)包含 CC 个整数 ai,1, ai,2,…,ai,Ca_{i,1},\ a_{i,2},\ldots,a_{i,C},用空格分隔,ai,ja_{i,j} 表示第 ii 行第 jj 列煎饼的状态。ai,j=1a_{i,j}=1 表示正面朝上,ai,j=0a_{i,j}=0 表示反面朝上。

输出格式

输出仅包含一个整数,即可出货煎饼的最大数量。

输入输出样例

  • 输入#1

    2 5
    0 1 0 1 0
    1 0 0 0 1

    输出#1

    9
  • 输入#2

    3 6
    1 0 0 0 1 0
    1 1 1 0 1 0
    1 0 1 1 0 1

    输出#2

    15

说明/提示

提示

注意 RR 的上限 1010 远小于 CC 的上限 10 00010\,000。

样例解释 1

- - - - - -

由 ChatGPT 4.1 翻译

输入解题思路,AI测评打分。不知道怎么写?

首页