QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#535488#1127. Virus ExperimentWansur100 ✓207ms71352kbC++233.0kb2024-08-28 05:20:322024-08-28 05:20:32

Judging History

你现在查看的是最新测评结果

  • [2024-08-28 05:20:32]
  • 评测
  • 测评结果:100
  • 用时:207ms
  • 内存:71352kb
  • [2024-08-28 05:20:32]
  • 提交

answer

#include <bits/stdc++.h>
#define f first
#define s second
#define ent '\n'
//#define int long long

using namespace std;
typedef long long ll;
const int maxn = 640000 + 12;

mt19937 rng(3124545533);
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
int u[901][901], pos[901][901];
bool used[901][901];
unordered_map<int, bool> can[maxn];
int val[maxn], p[maxn];
int sz[maxn], w[maxn];
int n, m, k;

int get(int x){
    if(p[x] == x) return x;
    return p[x] = get(p[x]);
}

void solve(){
    string s;
    cin >> k >> n >> m;
    cin >> s;

    val['W'] = 0;
    val['E'] = 1;
    val['N'] = 2;
    val['S'] = 3;
    while(s.size() <= 1e5){
        s += s;
    }

    for(int mask = 0;mask < 16; mask++){
        for(int i=0;i<s.size();i++){
            if(!(mask & (1 << val[s[i]]))) continue;
            int j = i;
            while(j + 1 < s.size() && (mask & (1 << val[s[j+1]]))){
                j++;
            }
            val[mask] = max(val[mask], j - i + 1);
            i = j;
        }
    }

    vector<pair<int, int>> t;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin >> u[i][j];
            t.push_back({i, j});
        }
    }
    shuffle(t.begin(), t.end(), rng);
    for(int i=1;i<=n*m;i++){
        pos[t[i-1].f][t[i-1].s] = i;
        p[i] = i;
    }

    reverse(t.begin(), t.end());
    int mx = 1e9, cnt = 0;
    for(auto [i, j]:t){
        if(!u[i][j]) continue;
        queue<pair<int, int>> q;
        q.push({i, j});
        used[i][j] = 1;
        int s = 0, tx = pos[i][j];

        vector<pair<int, int>> ord = {{i, j}};

        while(q.size()){
            auto [x, y] = q.front();
            q.pop();
            s++;

            for(int i=0;i<4;i++){
                int x1 = x + dx[i], y1 = y + dy[i];
                if(!used[x1][y1] && min(x1, y1) > 0 && x1 <= n && y1 <= m && u[x1][y1]){
                    int mask = 0;
                    for(int j=0;j<4;j++){
                        int x2 = x1 + dx[j], y2 = y1 + dy[j];
                        if(used[x2][y2]) mask |= (1 << j);
                    }
                    if(val[mask] >= u[x1][y1]){
                        if(get(pos[x1][y1]) < tx){
                            p[tx] = p[pos[x1][y1]];
                            break;
                        }
                        ord.push_back({x1, y1});
                        used[x1][y1] = 1;
                        q.push({x1, y1});
                    }
                }
            }
            if(p[tx] != tx) break;
        }

        if(p[pos[i][j]] == pos[i][j]){
            int sz = ord.size();
            if(mx > sz){
                mx = sz;
                cnt = 0;
            }
            if(mx == sz) cnt += sz;
        }
        for(auto [x, y]:ord){
            used[x][y] = 0;
        }
    }

    cout << mx << ent << cnt << ent;
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}

详细

Subtask #1:

score: 14
Accepted

Test #1:

score: 14
Accepted
time: 7ms
memory: 48716kb

input:

53768 10 50
EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE...

output:

1
10

result:

ok 2 lines

Test #2:

score: 14
Accepted
time: 128ms
memory: 56092kb

input:

10 800 800
WWWWEWWEWW
7 3 7 5 10 6 9 6 5 8 1 10 1 6 6 1 8 9 3 7 1 3 1 4 9 3 4 2 5 4 5 7 8 10 4 6 2 8 7 2 1 5 3 10 9 10 1 7 6 2 1 8 3 4 10 5 3 3 3 9 2 2 6 1 6 5 6 3 7 9 7 5 8 5 4 3 7 6 9 3 4 9 1 2 7 1 3 4 6 10 8 4 4 9 1 2 6 1 4 4 10 6 10 4 1 5 1 8 5 2 1 9 4 10 9 2 7 9 4 1 6 5 1 6 6 10 10 1 3 10 6 4 8...

output:

1
230450

result:

ok 2 lines

Test #3:

score: 14
Accepted
time: 142ms
memory: 58920kb

input:

10 800 800
WWWWWWWWWW
15314 11896 14475 25269 31478 32227 37443 24837 1353 32232 8163 3206 34713 17755 6870 20331 29572 19341 12557 36054 14768 990 30502 32464 15439 17070 15514 32216 37546 25514 27706 3028 26652 17247 13171 40866 36133 9550 22005 24048 33764 25331 12936 27462 27217 33096 19096 3919...

output:

1
800

result:

ok 2 lines

Test #4:

score: 14
Accepted
time: 134ms
memory: 57000kb

input:

31 800 800
EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

1
800

result:

ok 2 lines

Test #5:

score: 14
Accepted
time: 123ms
memory: 57528kb

input:

9999 800 800
WWWEEWEEWEWEEEWEEEWWWEWWEEEEEWEEEWWEWWWEWEWEWEEEWWWWWEWEEEEEEWEEWWEWWEEEEWEWWEWWWEEEWWEEWEWWWEWWEWWEEEWWWEWEEWWEWEWWWEWWWEEEWWEEEWWEEEWWWWEWWEWEWWWWEEWEEEWEWWEWEEWEWEEEWEWEEEWWWWEEEEWWWWWWEWWWEWEWWWEWEWWWEWWEEEEWWEEEEEWEWEWWWEWEEEEWEEEEWEEWEEEEEWEWWEEEWWEEEWEEEEWWEWWEEWEEWEWWEWWWEWEEEWE...

output:

1
639810

result:

ok 2 lines

Test #6:

score: 14
Accepted
time: 4ms
memory: 50968kb

input:

10 800 1
EWEWWWWWWW
1
1
1
0
1
0
0
0
1
0
0
0
1
1
1
0
0
0
0
1
0
0
0
0
0
0
1
1
0
1
1
0
0
1
1
0
1
0
1
0
0
0
0
1
1
1
1
1
0
0
1
1
0
1
0
0
0
1
0
0
0
1
0
1
1
0
1
1
0
1
1
1
0
0
0
0
1
1
0
1
0
1
0
0
1
0
0
0
1
1
1
1
0
0
1
1
1
1
0
0
1
0
0
1
1
1
0
1
0
1
0
1
0
1
0
1
0
0
0
1
1
0
0
1
1
1
0
0
1
1
0
0
1
1
1
1
1
1
1
0
...

output:

1
392

result:

ok 2 lines

Test #7:

score: 14
Accepted
time: 173ms
memory: 56704kb

input:

100000 800 800
WWEEWEEWEEEWEEWWWWWEEEWWWEEEWEWWEWEEEWWWEEEWEWWWWEEWWEWEEEEEEWWEEEWWWWWWWEWWWEEWWWWWWEEWEWEWEEWEWEWEWWEEEEWEEEEWEWWWWEEEEWWWEWWWEWWEWEWWWEWEWEWWEEEEEEWEEEEEWEEEEEWEEEWEEEEEEEWEWWWEWWWEWWWWEEWWEWEEEWWWWEEEEEEWWWEEEEEWEWEWWEWEEEEEEEWEEWWEWWEEWWEEEEEWWEWEWEEWWEEWEEWEWWWWEEWEWEWEEEEEEEWEW...

output:

800
640000

result:

ok 2 lines

Test #8:

score: 14
Accepted
time: 51ms
memory: 52424kb

input:

100000 500 500
EWWWEWEWEEWWEEEEEWWEWEEWEWWEEWEEEWEWWWWEWEWWWEWWEWEEWWWWWWWEEEEEEEEEWEEEEEEWEWWEEEEEEEWWEEEWWWEEWWEWEEWWEWWWWWWWWEWEEEWEWWWEWEWWEEEEEEEWWEEEWWWEEWWEEEWEWEWEWWWEWWWEEEWEEWWWWEWWEWWEWWEEEEWWEEWEEEEWEEWWEEEEWWWEWWWEWEWWEWWWEWEEEEEWWWEWEWEEEWWWEEEWEWWWEEWEWEEEWWWWEWEEWWEEWEEEWEWEWWEWEWWWE...

output:

1
227098

result:

ok 2 lines

Subtask #2:

score: 6
Accepted

Test #9:

score: 6
Accepted
time: 7ms
memory: 46680kb

input:

10 10 10
NNNNSENESS
3 2 0 0 1 3 2 3 1 2
3 3 2 0 5 2 4 0 5 1
5 1 2 3 0 4 4 0 1 0
5 0 1 0 2 4 2 2 0 3
0 1 0 1 4 0 1 4 1 0
3 5 5 0 2 5 3 0 3 4
5 3 1 0 5 4 4 0 4 4
1 0 2 0 5 4 0 2 3 0
4 2 0 2 3 0 2 5 5 4
3 0 2 0 5 4 5 4 0 5

output:

1
33

result:

ok 2 lines

Test #10:

score: 6
Accepted
time: 12ms
memory: 48720kb

input:

100000 10 10
NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN...

output:

1
10

result:

ok 2 lines

Test #11:

score: 6
Accepted
time: 11ms
memory: 46764kb

input:

100000 11 11
SWNESSSWNSEWNSNESSNWEWEWNSNNSWSSWSEEWNENWSWNNEWWSWNSESSEWENNESSENEEEESEESEWENEWSNSNNSSNNSWSNNSNESWEWSENNSESEEWWNESSNNWWSNWNNWNWNWWSEENNNWESSWNWNSEWWNWNNWSWSEWSENSNWNWNNEESSSENWWESSWEESWWENSSENWNNEESWENWSSSWEEWNWEWNNENNWSWEWSNNEESESNWNSEEENWWESSWEEWWSWESSNNEEWWNSSWSNEWSENSNNSENNSSNSSEEEE...

output:

27
27

result:

ok 2 lines

Test #12:

score: 6
Accepted
time: 3ms
memory: 49016kb

input:

100000 10 10
EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE...

output:

1
16

result:

ok 2 lines

Test #13:

score: 6
Accepted
time: 10ms
memory: 46972kb

input:

100000 1 1
WWSSSWEEEEESSNSSSSENWSESSNSWWSWESWSEEWSNSSEESSWESNNNENENWEENSSSSSNENESEESEWWSNNWSEWSWNWESSWNWSEESNSWSWENWEWNWESEWSSNSWENEWNNSWEEWWSSSWNSNWWWNSSWSSNSENESENNNENWESSENNEWENWEENWNWSSSWWWSNWESWEESNNNESNNEESNEWSSNNSSWSSESNSNNWENENEWWWSEESNWEWWNWNNSSNEEWSWNSWEESNSNSNEWNNWWWWSSWSWWESWWENSENWNWNWN...

output:

1
1

result:

ok 2 lines

Test #14:

score: 6
Accepted
time: 15ms
memory: 48812kb

input:

100000 50 50
ENWNNWEESNSNSSESSWNEWWESNWEENNEEWWEWNNESSSEWSWNWEWSSNEEWNSEWSSWNESWSWESEWWSENEWESEWSWSNNWWESSSWSSSESESNSSNESSSWSNWSSSENSWWNWNWNNNSNSNSEENWESENEENNESENSENNWEEESENWSESWSNWNNNSNSNWWENWEEEWSNWWEWSWNSEEEWEWWNSWNNNWWENSNSWWSNNWESNSSSWWNSEWSNWNEEESSEWEESENEESWSNNWSNESEESWEESNWSEEWWSSWESENESSSE...

output:

2500
2500

result:

ok 2 lines

Test #15:

score: 6
Accepted
time: 7ms
memory: 48812kb

input:

100 10 10
NENNWNSNNEWNENENNWWNEWNSNWWSSSNSNESSESWESSNNNNEWSWESNSNWSENWNSESNENWSWEWWWNSNWNWESNSESENNWNNWSSWSNSE
2 1 4 1 4 2 1 3 2 4
1 4 4 4 3 3 4 2 2 1
1 3 1 4 2 2 1 4 2 2
2 3 4 3 3 3 1 2 4 1
2 2 3 4 3 4 4 1 3 4
1 4 4 3 4 4 1 4 4 2
1 4 3 4 1 1 3 3 4 3
4 4 1 2 3 3 2 3 4 4
2 4 2 1 1 3 4 2 4 4
2 1 2 3 4...

output:

1
1

result:

ok 2 lines

Test #16:

score: 6
Accepted
time: 22ms
memory: 51068kb

input:

100000 50 2
ESNNNSWNNESEWSWWWSENWENSWSNSENSWSENWWNEENNWWNESWNWSEWSWWNSSWSSNENSWWWEEEEENSNWWNNESEWSSNSEEENWWNWWNEENSENWSWEWWNNWWNESSSNWNWWSEWEESESNEEEWNNWWEEEESWSEWWNNSNENWWSEEWNWSNWWEEWNSNWWWWWNWWNNSENNEWSEWENSSSSNWSSSNWSNSNEWESEESWWSEEWWWNWWNESNSNSSNEEWSSENNNEEENSNEEEESNSWNNESEENNEESNSSWENSWSWSNSEE...

output:

46
46

result:

ok 2 lines

Test #17:

score: 6
Accepted
time: 8ms
memory: 46692kb

input:

100 47 41
WWENEWENESSWWNESSENWNEWESWNWESNWNWSEWNEWNSWENSWSNNSWWNNENEWNWWWSWSSESSNEEWEENWEWNWENENESEENNWWWNSWEW
1 2 1 1 2 10 1 2 1 1 2 8 2 2 1 1 1 8 1 1 1 2 2 9 2 1 1 1 1 9 2 1 2 2 2 9 1 2 2 2 2
1 1 1 2 1 9 1 2 2 2 2 9 2 1 2 2 2 9 2 1 1 2 1 9 1 1 1 2 1 8 1 2 2 1 1 10 2 2 2 1 1
2 2 1 2 10 1 2 2 1 1 10...

output:

28
56

result:

ok 2 lines

Test #18:

score: 6
Accepted
time: 3ms
memory: 46736kb

input:

100000 10 10
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS...

output:

1
10

result:

ok 2 lines

Test #19:

score: 6
Accepted
time: 8ms
memory: 48708kb

input:

10 50 50
ESSSSSSSEE
4 2 10 7 7 1 8 1 2 4 8 4 4 2 9 7 3 9 7 3 9 3 4 6 7 2 5 2 4 8 5 2 2 10 10 6 2 1 1 5 10 7 3 10 10 10 6 8 7 7
9 3 9 6 1 7 10 9 8 7 2 1 10 8 4 4 10 8 10 5 2 7 6 6 3 10 2 4 1 3 3 2 8 3 9 1 7 2 3 8 7 7 1 5 3 7 5 2 10 5
1 2 10 1 1 4 1 5 1 10 10 10 10 2 7 5 1 8 8 5 5 3 4 5 1 3 5 6 1 6 8 ...

output:

1
545

result:

ok 2 lines

Test #20:

score: 6
Accepted
time: 8ms
memory: 46864kb

input:

100 50 50
WWWNSWNWWESSSESNEWESENENWESESSEENNWNWNSWESENEEEESWEENWSWWWWNEENEEWSSWNWNWNEESEEENWENSENSESSSWNWSSNSW
1 1 2 1 2 1 1 2 1 2 2 1 2 2 2 1 1 2 2 2 1 8 2 1 2 2 2 1 2 1 1 2 2 2 1 1 1 1 2 1 1 2 1 1 1 2 1 2 2 2
1 2 1 1 1 2 2 1 1 2 2 1 2 1 2 1 2 1 1 1 2173 2 2 1 1 2 1 2 1 2 1 1 2 2 2 2 1 1 1 1 1 1 1 ...

output:

2500
2500

result:

ok 2 lines

Test #21:

score: 6
Accepted
time: 14ms
memory: 48688kb

input:

100000 50 50
WWSNNSSSSSSSWWWSWSNNNNSSNNSSNWWNSSNNNSSSSWSWWSNNSNWSNWNWNWSSWWNWWNNSWWSSSWSNWNWSWWNNNNWSSSNSSNNNSSSNSWSWSWWWWSSNNNSWNSNSSSWSWNNWNSNNWSNWSSSWSWWSWNWSWWNNNSSWWSNWSWSNWNNWNSNSSSNNNNWNSWWWNNSWNWWNNSWWNNWNWSNSSWNWNWWWSNSWSNWNSWSWSNWNNNWNSNSSWWNSNWSWNWNSWNNSSWNSNNWSNSWWWWSSWSNNNNSSWWWWNSWNWSW...

output:

50
50

result:

ok 2 lines

Test #22:

score: 6
Accepted
time: 14ms
memory: 48780kb

input:

100000 50 50
SWSSSNWSNWNNNSNSSSNNSWNNWNWWNSNNNSNNWNNSNWNWSNSWWNSWWNSSWNWNWSWNNSSNNWSWSNNNNWWSNSSSSWSSWWSNNWWSNNWSSSSSSWNNWSWWSWWWWNSNSNWWWSSWWNNSSWSNWNSNSNNSWSWWWNSWWNSNSSNSWSNNSWNWSSNWWSSSNWNWSWSNSNSSWWNNWWWWNNNSWWWNWWNSWWNNWSNNSNNWNSSNWWNNSSNSSNSSSNWSNSSWWWNNNSSWSWNNSNSNWSNSNSSWSSSSWSWNNNNWSWWSNNW...

output:

1
3

result:

ok 2 lines

Test #23:

score: 6
Accepted
time: 17ms
memory: 51028kb

input:

100000 50 50
NNEENENWWNWNNEEWNNWWWWNENNWWNENWNNWNNWWENEENNNEEEWENEENENWNEEEENNEWEWEWNNWNNNEWNWEWNNENWWWWWEENNNNENWWWNENNENENWENNWNWEEEEEWNWWWEWWEWENEENNWEEWWWEEENWNNEENEEEEEWWWWEEEEWWWEEEEWWNNNNEEEWNEWEWENEWEWNEEWNWENWNWEWENNENNWNWEWWENNEWNNNNNNNENNENNNNWEENNNWWWWNNENEEEWNWNWEWNNWNNENWWWWNWNEENWWWEN...

output:

50
50

result:

ok 2 lines

Test #24:

score: 6
Accepted
time: 16ms
memory: 46936kb

input:

100000 50 50
SESWSSWEWEWSWESWEEEWESESSEWEWWSEEEWSESEWSESWWSWEWSSSWSEWESSWSSWSWWWWESEEWEWEWEEEWEEEWWSEEESSEESEEWSESSWEEEWWWSEWSWWSEWSWWEESSWSEEEEEWSSWEWEEESEEWSSWSEWESEWSSEWWSWEWSWESESEEWEEEWESWEESWSESWWSWSWEWESWESEESESSWSESESESSEEWWSSWESEWSWSSSEWWWWSSESSSEESSWWWSEWSSSSESWSSSSEESWSSEWSSSEEESWESWSEEWE...

output:

1
37

result:

ok 2 lines

Test #25:

score: 6
Accepted
time: 19ms
memory: 48780kb

input:

50000 50 49
SNNWEENNESEEEWSESNWSENSSWNWWENENWWEWSEWEEENSNSWEEEESENEEENNSSSESSNEEWSWEWWNSSWNNNSNNNWSSSNEWSSSESWSSWNSSESSNESESWESSWWSEENWENWWENWEWWNNWNWNWEESSSEWWSSSWNSEESWEENNENWEWNNEESSNWSNWSWWWSENWSESSNNNSESNESNSNSWSSNNSNWWEEESESSNNESSWNEENWEESESWSNWNENWNENEEENNSEEESEWENSESWENENSENSWNEEEEWNNSWNNSNN...

output:

3
915

result:

ok 2 lines

Test #26:

score: 6
Accepted
time: 12ms
memory: 46944kb

input:

2000 50 50
NNWSNWWSWNNSNWNNNENWNSWSENSWWSNWNWSSSWNESNSWSENWSNWWSWWENWSWNENWSWENSSSSWNWSNWESWNSNWESSEEEEEESNWNNESENNWNNESNSWNNNNESSWNNENEWSNESSNWNNENEEWWEWNEWNSSWSSSEWEESSNEWSEWNSSSWWSNEWEEWESENNSNSNWSWWENNWNSWSWNESEWNEWESWESSESWNEWNESNNWESSSSENSSSESNWNSNWSNNSESESSSNWNEEWNWSNNWEEWSEWEENSNWSESSESEWENN...

output:

50
1400

result:

ok 2 lines

Test #27:

score: 6
Accepted
time: 17ms
memory: 46700kb

input:

100000 50 50
NNNNSENESSEEWWNSESWWNNEEWSEWSEWNWNEESWNEENWWNNWWEWWNNENNWSWSNNEENWSNSSNSNSSNSSWESWEWSWWSENWNWSENWWWSSESENNWNNWESNWEEESNESSWEWSSNESSEEEEWEWESNSNWEEWNWNSENSSNNESEEWESENENESSNNSWWEWWNWNEWENSNWENWEENNNSWSENWWSWENNWSESNSNSWSSSENSSSENNWWEESENSSNESNNSESNNWNWNEESEWWSEWWESEWSEEWWSSNENSNWWSNEENEW...

output:

1
2262

result:

ok 2 lines

Subtask #3:

score: 80
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #28:

score: 80
Accepted
time: 187ms
memory: 69452kb

input:

100000 800 800
SSENEWWEWNSESESSNSEESSEEWESWESNNWWNSEWENENSSEEWESNWSNENSSSNNWNENENSNWWNENESNWNEWSEWNENNWWWNSSSWENNWWEWSSWNNSSSNNNESEENWWNWSSWNEWSWNSSWEESESWESWSENNNSWNNWNENNWWWWSEWNEWWEWNESNSNSWWSEEESWWWWSNNNEEWNWWEWENSSNNNSSEWWSWENENNNSWESWEEEWWEEENSSSSNEEWNNNWWWWSEEWNWNENSEWEWNEWSESNEWNNENSNWEWNNSN...

output:

640000
640000

result:

ok 2 lines

Test #29:

score: 80
Accepted
time: 156ms
memory: 70804kb

input:

100000 800 800
NNSWSNENNEWNWWWWEWNWWSNEWWWNSNEWEWSEWWSEESEEWENESSWWSWSSNEESENWENNESWNESSSENWSWWNWNSNSSNWSNEWWSENNWWEWNEWEWNNNNEWSNEESESWEESNSWNEWWWWNWWESNWNNESNEWWEENWSSENSSWNEENESSWNSESESWSSSEWSWSWWNEWWSSWNNWEWNENWNESWNESNSWENWSSNNWSNWNSESWNWNEESWNEWWENEWWNSEEEWWSSWNSSESWNENSWSSNWEENNWWENENNSNWENWW...

output:

1
3

result:

ok 2 lines

Test #30:

score: 80
Accepted
time: 119ms
memory: 58988kb

input:

100000 800 800
NWWWNWENNENNNWWEWWWWNEWWEWWWEWENEWNWNNNEWENEWWNWWNEENNWWWENEENNENEENWWNNEWWEEWNWEENEWWENWNENEEWWNENWEEWWNWWWNWENNEEEEEWWWNENEWEEEEENNNWNEENNWNNWNEWWEEENENENNWEWNNWNWNNNEEWEWEEEENEWWENENNENNWWENWNNEWNNEENWEEENENWNWENNWNWWEEENWEEEWNENEWNNNWNEENNNWNEWNNWNEWNNENWNEWNEWNNWWENENWENWENWWEEWE...

output:

800
800

result:

ok 2 lines

Test #31:

score: 80
Accepted
time: 189ms
memory: 58656kb

input:

100000 779 785
NWNNNNWSENEWWNENWSSESSNWSNWWNEWNSWNNEWSWNNEEWWSWNSWWEESWENNWWSSWNNSWSSEENSEWWNNWSSSWNNEESNWWSWWWNEENESWNNENWESNWWWEWSNNSENNEESNSSSESWWWWSESNNWWENNWEWNSEESWESSSSNNSNSWSNNWEEEWNENWWNSNSWWWENNSSWSEWWNNEENWWEEEEEEWWWSNENSWSESNWSNNWSSNESWNWSNEENWSSNENEWWWSSSEWNNNESEESEWSWSWSSWNWWNEEWNNSWWE...

output:

28
2100

result:

ok 2 lines

Test #32:

score: 80
Accepted
time: 207ms
memory: 60888kb

input:

100 791 797
WWWENSWEEWNESSSSSWSEENENNSWENEEWWEWSNNSESNNNESENESNWSSWNSSWWWSSNEEEWWNESNSNWESSNSNESEENSNNEWNSSWSENS
1 3 3 2 1 9 3 1 3 1 1 9 1 3 1 1 3 8 1 2 1 3 2 8 3 3 2 1 3 9 1 1 1 3 2 8 1 3 2 2 1 9 3 2 2 1 3 8 1 1 1 3 2 9 2 2 2 1 2 9 1 1 3 3 3 8 3 3 2 1 3 8 2 2 2 1 3 9 2 2 2 3 1 9 2 1 3 1 3 8 3 1 1 1...

output:

27
27

result:

ok 2 lines

Test #33:

score: 80
Accepted
time: 146ms
memory: 57440kb

input:

10 800 800
EEEEEEESSS
10 1 6 1 6 8 6 4 7 9 2 10 2 10 8 8 1 9 1 1 2 2 2 2 9 4 4 6 10 7 7 1 6 1 2 5 2 10 6 7 10 1 3 10 7 1 9 9 1 6 10 10 2 2 3 2 4 4 1 1 7 8 8 7 9 7 1 2 5 3 3 8 9 2 4 8 2 2 9 4 6 10 3 9 4 5 3 1 1 1 3 10 5 7 8 2 5 4 10 8 7 9 5 8 9 9 1 4 9 10 8 9 8 9 7 7 1 9 10 1 4 2 3 4 7 8 6 10 6 3 3 2...

output:

1
134814

result:

ok 2 lines

Test #34:

score: 80
Accepted
time: 191ms
memory: 71352kb

input:

100 800 800
NWWSSNENSWNNWEWESESWWSNWWSNESEEWWEEENEWWNNSSNNESNWNNNWSSEEEWENWWNSNESWSNWSNWWWSWESNESSESSSESNEWNSSNN
3 2 2 3 2 2 3 3 1 2 1 3 3 1 2 1 3 2 2 2 3 3 1 3 2 1 2 2 2 3 2 1 3 2 1 1 3 1 3 1 2 2 3 3 2 3 3 2 2 1 2 1 2 2 1 1 2 3 1 3 1 3 3 2 1 2 2 1 1 1 1 2 2 3 3 2 1 1 1 1 2 3 1 3 3 1 1 1 2 3 3 1 1 2...

output:

640000
640000

result:

ok 2 lines

Test #35:

score: 80
Accepted
time: 97ms
memory: 59664kb

input:

200 612 800
NSSEWNSWWNSSWNWWEEWSSWSNESWEWSENEWEWNSNWWEWNNWSSNSENWWNWENSSWESENNWNSWENWWSEWNNSWWWEESWNENWEWNWSNWWEWWSENWNENEENWEEWSEWWESWWWWNNWENEEWSSNWSNWEEWWWNESESSWESEWNSNNENSSNEEEEEENENEWWESNWEEESSNWENEWESENWSW
2 1 2 13 2 2 2 2 2 1 2 2 2 2 1 1 1 2 1 2 2 2 1 2 2 1 2 1 1 1 2 2 1 1 1 1 2 1 1 1 1 2 2 ...

output:

489600
489600

result:

ok 2 lines

Test #36:

score: 80
Accepted
time: 185ms
memory: 55904kb

input:

49 800 800
WEEWNNSWSWENSNNWSSESNENNSNSWNSESSSSWWNNSNNEENESWW
2 2 2 2 14194 2 2 1 2 1 13890 2 2 2 6 2 1 6592 14012 7199 2 2 2 1 2 1 2 6313 2 1 2 3 2 1 1 1 2 2 2 2 12166 1 1 1 2 1 1 2 2 1 2 1 1 1 2 1 2 1 2 1 2 2 1 1 1 2 1 1 1 1 2 1 2 2 1 1 1 1 13978 2 1 1 1 1 2 1 1 1 2 2 1 2 1 2 2 1 1 2 2 2 2 2762 435...

output:

768
409344

result:

ok 2 lines

Test #37:

score: 80
Accepted
time: 159ms
memory: 59072kb

input:

100 800 800
SNNSSWNSNWSWNSNWSSSWNESWWENSSNWNEWNEWSEWEESSSSWWNNWWWNNNNSWNWNSSWNSENEWSSWNNNEENWNWNNWNNNWWSNNNNWNSS
1 2 2 2 2 1 1 2 2 2 2 2 2 2 1 2 2 1 2 1 1 2 2 2 2 1 2 2 2 2 1 1 2 1 1 1 2 1 2 1 1 2 1 1 1 2 1 1 2 1 1 2 1 1 2 2 2 2 2 1 1 2 2 1 1 1 1 1 2 2 1 1 2 2 2 2 2 1 1 1 1 1 2 1 1 2 2 1 1 1 2 33834...

output:

225000
450000

result:

ok 2 lines

Test #38:

score: 80
Accepted
time: 134ms
memory: 68532kb

input:

800 800 800
NSNSNENNNNEWSNNENNSSSEWWSNESEENSWWENNNENEWNSNSNWESEWWESENESWWSWENEWWWWSESSENEWSSSWNSEWWNNWSEESSNNNWEEWEENESESSWENNNSENNEWWNWNEEWSSNNWSSNEWEESSNWWWNESNWSESWSSNENSNSWSSWESNNWNESSESWWSWSNWEEWENNNNENNEWWENEENNSWSNNNSWEEESSNSNSWSNSWENSEWSESENWSEWNNENWWWSNESNWSEWSSSWWENNNNSSSNNENEWWNEEEEESSNEW...

output:

635256
635256

result:

ok 2 lines

Test #39:

score: 80
Accepted
time: 166ms
memory: 56116kb

input:

100000 800 800
WSENNSNEESNNWNEENNSSSSSNWESSSSWEEWNENSNSWSWNNSSSSNSSWNEWESNNESEWESESWWSENEWNWEEEWESNWSWNNSENEEWENNSSWENESNEEENESSWESNNWESENWWENNWNESWSSEWNWENEWENSNWNWNESEWSNNNWNSSEWNNSWWSESENNSSEEWENWWWEWWSNSEEWESSNESESWWNWWESNSESEWSWNNNEWWNWWEEWWSNNWESWNENSEWSWWNSENWEWSEENEESNNEWWNNNNEEWESESNNSSWEEN...

output:

2
210940

result:

ok 2 lines

Test #40:

score: 80
Accepted
time: 188ms
memory: 56116kb

input:

100000 800 800
NEWNNNSEWNEWNEWWSWSWNNNWWNSESWEWSEWNNSWWNSWWEWWWNSSSWWWNNWWWWSEESNENWEEWNNWNNESEENSNEENSNENWSNENNENEWWWSESSESNESEEEESNEWWSSNEWENWNNENNWSSWENENESNEEEWWEEESNSESSEWWSEWSNSNWWESWWNSSSSWNWEWWSNWSSNNNSNWENWEESWNNNNEWNSWWWSWSWSNNSWNEWEEESNWENSWSWSWSEWSNNNWNNNEEWWWSWNWWWSSWSSSNEWSSEWEWSEWNSES...

output:

4
251772

result:

ok 2 lines

Test #41:

score: 80
Accepted
time: 152ms
memory: 54980kb

input:

50000 800 800
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS...

output:

1
53315

result:

ok 2 lines

Test #42:

score: 80
Accepted
time: 172ms
memory: 63300kb

input:

100000 800 749
EWNSSNSNESNNSNSNEWEWSSEWWENWWESNNENWESESSNESEEWWSSSWEESWSESEWENEEWSNNWEENNESESSWNNESSENEENEEENSEEEESWNSSSWSSESNWNWESWNWENNEWNWWSNSWNSSWNNSNSESNESWSNSSWEESSNWSWWSEWNWWENWWNNESSWNSNSWEWNNWNNWSNNEWEWNSSNSSENWWESNSSSNWENNWNEWNESSESSNWNESWWNNSSEWSWWWSENNNNEWSNESENNEENENWSWWSEWSEWSNSNNWEESE...

output:

1
1767

result:

ok 2 lines

Test #43:

score: 80
Accepted
time: 201ms
memory: 66828kb

input:

100000 800 800
SNSWWNNSSSWNWNNNSSWWWNSSWWSWWWWWWWSSNNNSWNNSNNSWNSNWNNSSWWSWSWWNSNWNSWNSSNSWWWNSSWWSSSWWSNNNNSNNNWSSWNWNSSSSNSNWSSNSSSSNSSWSSWWWNSNWNNSSNSNNNWNSNNWWNNNNWWSNWSSWSSWWNSSSWSWSWWSSSNNSNNNNWSWWSSNWSSSNWWWWNNWWSSWWNWNSNSWSNSWWWWNWWSNNNNWWSWWNWNSWWNNSNSWNNNSWWSNNNNNSWWWNSSNSNNWNNWNNSNSWSNWWW...

output:

1
1054

result:

ok 2 lines

Test #44:

score: 80
Accepted
time: 54ms
memory: 52616kb

input:

100000 500 500
SSENEWWEWNSESESSNSEESSEEWESWESNNWWNSEWENENSSEEWESNWSNENSSSNNWNENENSNWWNENESNWNEWSEWNENNWWWNSSSWENNWWEWSSWNNSSSNNNESEENWWNWSSWNEWSWNSSWEESESWESWSENNNSWNNWNENNWWWWSEWNEWWEWNESNSNSWWSEEESWWWWSNNNEEWNWWEWENSSNNNSSEWWSWENENNNSWESWEEEWWEEENSSSSNEEWNNNWWWWSEEWNWNENSEWEWNEWSESNEWNNENSNWEWNNSN...

output:

1
227231

result:

ok 2 lines