logo AlgoBeat OnlineJudge
登录 注册

#214374. [ROI 2015 Day2] 潜水艇

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

译自 ROI 2015 Day2 T2. Подводная лодка


一艘潜艇搁浅在浅海海底。为了探测其位置,科学家使用了卫星数据——卫星可以高精度地测量海面相对于平均海平面的高度偏差。卫星拍摄的图像可以表示为一个包含 行、每行 个元素的数组。

:::align{center} :::

在该图像上建立坐标系:横坐标轴( 轴)沿行方向,从左向右;纵坐标轴( 轴)沿列方向,从下向上。

潜艇的潜在图像定义为由以下部分组成的元素集合:

  • “艇身”:由坐标从 的元素构成的一条水平带,且
  • “指挥塔”:由坐标从 的元素构成的一条垂直带,其中 ,且
  • “尾部”:由坐标从 的元素构成的一条垂直带,其中 ,且

由于潜艇位于浅水且水流湍急的区域,潜艇上方的水面会略微隆起。因此,我们将图像中潜艇的表示定义为这样一个潜在图像,其对应数组元素的数值和最大

你的任务是编写程序,在图像中找到这样的潜艇图像,并输出其元素之和。

输入格式

为了压缩从卫星传输的数据,图像中的每个元素以英文小写字母进行编码。

  • 第一行包含整数 —— 用于编码的字母数量()。
  • 第二行包含 个整数 —— 分别表示前 个英文字母(从 a 开始)的高度偏差值。
  • 第三行包含两个整数 —— 图像的行数与列数。
  • 接下来的 行中,每行包含 个字符,表示图像的编码内容。

输出格式

输出一个整数 —— 对应于潜艇图像的数组元素之和的最大可能值。

样例

样例输入 1

2
-10 1
6 11
aaaaaaaaaaa
aaabaaaaaaa
aaabaaaabaa
abbbbbbbbba
aaaaaaaabaa
aaaaaaaaaaa

样例输出 1

13

样例输入 2

3
-4 -3 4
5 5
bbabc
ccaac
accba
baccb
baaaa

样例输出 2

16

样例输入 3

3
-2 4 0
5 5
abccb
cccac
cbcba
cccbb
accba

样例输出 3

24

样例输入 4

4
-1 -5 -3 0
5 5
bbabc
ccaac
acdba
baccb
baaaa

样例输出 4

-2

数据范围与提示

样例解释

样例 1-4 的图像分别如下:

...........
...b.......
...b....b..
.bbbbbbbbb.
........b..
...........
.....
.c...
.cc..
..c..
.....
.b...
.c...
.b.b.
cccbb
...b.
.....
..aa.
.....
.....
.....

下面展示了几个潜在的潜艇图像示例:

:::align{center} :::

以下是一些不是潜在潜艇图像的示例:

:::align{center} :::

评分标准

子任务编号 分值 范围 范围
1 32
2 22
3 23
4