#P10386. [2021年联测]病毒

    ID: 9504 传统题 1000ms 512MiB 尝试: 5 已通过: 1 难度: 9 上传者: 标签>CF2700省选/NOI-随机排列队列状态编码增量维护时间戳避免清空数组复制数组处理环期望线性性

[2021年联测]病毒

题目背景

有一个矩形网格,共 nn 行 mm 列,每一个格子里有一只实验用的小白鼠。每一天被划分为 kk 个时间段,每个时间段都会吹风,风总会从东南西北四个方向之一吹来,每个时间段吹的风只与该时间段的编号有关,与天数无关,并且第 ii 天的最后一个时间段紧接着第 i+1i+1 天的第一个时间段。

每只小白鼠有对病毒的抵抗力,可以量化为一个非负整数,第 ii 行第 jj 列的小白鼠对病毒的抵抗力为 ai,ja_{i,j}。

  • 若 ai,j=0a_{i,j}=0,表示这只小白鼠抵抗力很高,无论如何都不会感染病毒。
  • 否则若连续 ai,ja_{i,j} 个时间段满足如下条件这只小白鼠就会被感染:这个时间段风的吹来方向相邻的小白鼠感染了病毒。

为了完成这个实验,你需要在一开始就使恰好一直小白鼠感染病毒,注意你不能使抵抗力为 00 的小白鼠感染。

你是富有人道主义的,对小白鼠也是如此,所以你想让被感染的小白鼠尽可能少。为此,你需要求出 1010010^{100} 天后最少被感染的小白鼠个数以及达成此最小数量的初始感染者选择方案数。

输入格式

第一行三个正整数 k,n,m(1≤n,m≤800,1≤k≤105)k,n,m(1\le n,m\le 800,1\le k\le 10^5)。

第二行一个长为 kk 的仅有 N,S,W,E 组成的字符串,第 ii 个字符表示每一天的第 ii 个时间段风吹来的方向,N 代表风从北吹来,S 表示风从南方吹来,W 表示风从西吹来,E 表示风从东吹来。

接下来 nn 行每行 mm 个非负整数,第 ii 行第 jj 个表示 ai,j(0≤ai,j≤105)a_{i,j}(0\le a_{i,j}\le 10^5)。

输出格式

两行,每行一个整数。

第一行输出 1010010^{100} 天后最少被感染的小白鼠个数,第二行输出达成此最小数量的初始感染者选择方案数。

样例输入 1
6 3 4
SWNEES
2 1 1 2
1 0 1 3
1 1 2 2
样例输出 1
8
8

数据范围与约定

subtask1(2020 分):风只会从西方或者东方吹来。

subtask2(1010 分):n,m≤50n,m\le 50。

subtask3(7070 分):无特殊限制。

对于 100%100\% 的数据,保证 $1\le n,m\le 800,1\le k\le 10^5,0\le a_{i,j}\le 10^5$,至少有一个 ai,ja_{i,j} 不为 00。