← 返回题目列表

AtCoder · jag2017summer_day3_g

G. 低范围求和矩阵

中文机器翻译题面 查看原题

问题陈述

您在宴会上收到了一张卡片。卡片上写有 $N$ 行和 $M$ 列的矩阵以及两个整数 $K$ 和 $S$。矩阵中的所有元素都是整数,从上起第$i$行、从左起第$j$列的整数记为$A_{i,j}$。

您最多可以从矩阵中选择 $K$ 个元素并反转元素的符号。如果您可以制作一个矩阵,使得没有垂直或水平连续子序列的总和大于 $S$,您就可以用您的卡换取奖品。

您的任务是确定您是否可以用给定的卡片交换奖品。


输入

输入由以下形式的单个测试用例组成。

$N$ $M$ $K$ $S$ $A_{1,1}$ $A_{1,2}$ $\cdots$ $A_{1,M}$ $\vdots$ $A_{N,1}$ $A_{N,2}$ $\cdots$ $A_{N,M}$

第一行由四个整数 $N$、$M$、$K$ 和 $S$ 组成($1 \le N、M \le 10$、$1 \le K \le 5$、$1 \le S \le 10^6$)。 以下 $N$ 行代表卡中的矩阵。 第 $(i+1)$ 行由 $M$ 个整数 $A_{i,1}$、$A_{i,2}$、$\ldots$、$A_{i,M}$ ($-10^5 \le A_{i,j} \le 10^5$) 组成。

输出

如果您可以用卡片换取奖品,请打印 Yes。否则,打印 No.


示例输入 1

3 3 2 10
5 3 7
2 6 1
3 4 1

样本输入 1 的输出

Yes

从 $A_{1,1}$ 到 $A_{1,3}$ 的水平连续子序列的总和为 $15$。从 $A_{1,2}$ 到 $A_{3,2}$ 的垂直连续子序列的总和为 $13$。如果翻转 $A_{1,2}$ 的符号,则不存在总和大于 $S$ 的垂直或水平连续子序列。


示例输入 2

2 3 1 5
4 8 -2
-2 -5 -3

样本输入 2 的输出

Yes

示例输入 3

2 3 1 5
9 8 -2
-2 -5 -3

样本输入 3 的输出

No

示例输入 4

2 2 3 100
0 0
0 0

样本输入 4 的输出

Yes