QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#283627#1127. Virus ExperimentMax_s_xaM100 ✓101ms18388kbC++145.3kb2023-12-14 23:10:382023-12-14 23:10:38

Judging History

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

  • [2023-12-14 23:10:38]
  • 评测
  • 测评结果:100
  • 用时:101ms
  • 内存:18388kb
  • [2023-12-14 23:10:38]
  • 提交

answer

#include <iostream>
#include <algorithm>
#include <queue>

typedef long long ll;
typedef double lf;

// #define DEBUG 1
struct IO
{
    #define MAXSIZE (1 << 20)
    #define isdigit(x) (x >= '0' && x <= '9')
    char buf[MAXSIZE], *p1, *p2;
    char pbuf[MAXSIZE], *pp;
    #if DEBUG
    #else
    IO() : p1(buf), p2(buf), pp(pbuf) {}
    ~IO() {fwrite(pbuf, 1, pp - pbuf, stdout);}
    #endif
    #define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) ? ' ' : *p1++)
    #define blank(x) (x == ' ' || x == '\n' || x == '\r' || x == '\t')

    template <typename T>
    void Read(T &x)
    {
        #if DEBUG
        std::cin >> x;
        #else
        bool sign = 0; char ch = gc(); x = 0;
        for (; !isdigit(ch); ch = gc())
            if (ch == '-') sign = 1;
        for (; isdigit(ch); ch = gc()) x = x * 10 + (ch ^ 48);
        if (sign) x = -x;
        #endif
    }
    void Read(char *s)
    {
        #if DEBUG
        std::cin >> s;
        #else
        char ch = gc();
        for (; blank(ch); ch = gc());
        for (; !blank(ch); ch = gc()) *s++ = ch;
        *s = 0;
        #endif
    }
    void Read(char &c) {for (c = gc(); blank(c); c = gc());}

    void Push(const char &c)
    {
        #if DEBUG
        putchar(c);
        #else
        if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
        *pp++ = c;
        #endif
    }
    template <typename T>
    void Write(T x)
    {
        if (x < 0) x = -x, Push('-');
        static T sta[35];
        int top = 0;
        do sta[top++] = x % 10, x /= 10; while (x);
        while (top) Push(sta[--top] ^ 48);
    }
    template <typename T>
    void Write(T x, char lst) {Write(x), Push(lst);}
} IO;
#define Read(x) IO.Read(x)
#define Write(x, y) IO.Write(x, y)
#define Put(x) IO.Push(x)

using namespace std;

const int MAXR = 810, MAXN = 64e4 + 10, MAXM = 1e5 + 10;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int M, n, m, rs[MAXR][MAXR];
char dir[MAXM << 1];

inline int Tr(char ch) {return (ch == 'N' ? 0 : ch == 'E' ? 1 : ch == 'S' ? 2 : 3);}
int mxlen[18];
inline int C(int i, int j) {return (i - 1) * m + j;}
inline pair <int, int> C(int x) {return make_pair((x + m - 1) / m, (x - 1) % m + 1);}

int fa[MAXN];
int Find(int k) {return k == fa[k] ? k : fa[k] = Find(fa[k]);}
inline void Union(int u, int v)
{
    u = Find(u), v = Find(v);
    if (u != v) fa[u] = v;
}

int cnd[MAXN], top, mch[MAXN];
int vis[MAXN], idx;
queue < pair <int, int> > q;
inline bool Check(int x, int y)
{
    if (x < 1 || x > n || y < 1 || y > m) return 0;
    int s = 0;
    for (int i = 0; i < 4; i++)
    {
        int xx = x + dx[i], yy = y + dy[i];
        if (xx < 1 || xx > n || yy < 1 || yy > m) continue;
        // cout << xx << " " << yy << " " << vis[C(xx, yy)] << "\n";
        if (vis[C(xx, yy)] == idx) s ^= (1 << i);
    }
    // cout << "Check " << x << " " << y << " " << s << " " << idx << "\n";
    return mxlen[s] >= rs[x][y];
}
inline pair <int, int> BFS(int st)
{
    auto cur = C(st); int x = cur.first, y = cur.second;
    int cop = Find(st), sz = 0;
    if (rs[x][y] == 2e9) return make_pair(-1, 2e9);
    while (!q.empty()) q.pop();
    q.push(cur), vis[C(x, y)] = ++idx;
    while (!q.empty())
    {
        cur = q.front(), x = cur.first, y = cur.second, q.pop();
        // cout << x << " " << y << " " << idx << "\n";
        sz++;
        for (int i = 0; i < 4; i++)
        {
            int xx = x + dx[i], yy = y + dy[i];
            if (vis[C(xx, yy)] == idx) continue;
            if (!Check(xx, yy)) continue;
            if (Find(C(xx, yy)) != cop) return make_pair(C(xx, yy), 0);
            q.push(make_pair(xx, yy)), vis[C(xx, yy)] = idx;
        }
    }
    return make_pair(-1, sz);
}

int main()
{
    // freopen("tmp.in", "r", stdin);
    // freopen("tmp.out", "w", stdout);
    #if DEBUG
    #else
    ios::sync_with_stdio(0), cin.tie(0);
    #endif
    Read(M), Read(n), Read(m);
    Read(dir + 1);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            Read(rs[i][j]);
            if (!rs[i][j]) rs[i][j] = 2e9;
        }
    for (int i = 1; i <= M; i++) dir[i + M] = dir[i];
    for (int s = 1; s < 16; s++)
    {
        int cnt = 0;
        for (int i = 1; i <= 2 * M; i++)
            if (s & (1 << Tr(dir[i]))) cnt++, mxlen[s] = max(mxlen[s], cnt);
            else cnt = 0;
        if (mxlen[s] == 2 * M) mxlen[s] = 1e9;
    }
    for (int i = 1; i <= n * m; i++) fa[i] = i;
    while (1)
    {
        top = 0;
        for (int i = 1; i <= n * m; i++)
            if (fa[i] == i) cnd[++top] = i;
        for (int i = 1; i <= top; i++) mch[cnd[i]] = BFS(cnd[i]).first;//, cout << cnd[i] << " " << mch[cnd[i]] << "\n";
        bool flag = 0;
        for (int i = 1; i <= top; i++)
            if (~mch[cnd[i]]) Union(cnd[i], mch[cnd[i]]), flag = 1;
        if (!flag) break;
    }
    int mn = 1e9, ans = 0;
    for (int i = 1; i <= n * m; i++)
        if (fa[i] == i)
        {
            auto cur = BFS(i);
            if (cur.second < mn) mn = ans = cur.second;
            else if (cur.second == mn) ans += cur.second;
        }
    Write(mn, '\n'), Write(ans, '\n');
    return 0;
}

详细

Subtask #1:

score: 14
Accepted

Test #1:

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

input:

53768 10 50
EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE...

output:

1
10

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 53ms
memory: 17484kb

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: 0
Accepted
time: 22ms
memory: 17368kb

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: 0
Accepted
time: 25ms
memory: 18388kb

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: 0
Accepted
time: 82ms
memory: 17420kb

input:

9999 800 800
WWWEEWEEWEWEEEWEEEWWWEWWEEEEEWEEEWWEWWWEWEWEWEEEWWWWWEWEEEEEEWEEWWEWWEEEEWEWWEWWWEEEWWEEWEWWWEWWEWWEEEWWWEWEEWWEWEWWWEWWWEEEWWEEEWWEEEWWWWEWWEWEWWWWEEWEEEWEWWEWEEWEWEEEWEWEEEWWWWEEEEWWWWWWEWWWEWEWWWEWEWWWEWWEEEEWWEEEEEWEWEWWWEWEEEEWEEEEWEEWEEEEEWEWWEEEWWEEEWEEEEWWEWWEEWEEWEWWEWWWEWEEEWE...

output:

1
639810

result:

ok 2 lines

Test #6:

score: 0
Accepted
time: 0ms
memory: 13748kb

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: 0
Accepted
time: 64ms
memory: 17800kb

input:

100000 800 800
WWEEWEEWEEEWEEWWWWWEEEWWWEEEWEWWEWEEEWWWEEEWEWWWWEEWWEWEEEEEEWWEEEWWWWWWWEWWWEEWWWWWWEEWEWEWEEWEWEWEWWEEEEWEEEEWEWWWWEEEEWWWEWWWEWWEWEWWWEWEWEWWEEEEEEWEEEEEWEEEEEWEEEWEEEEEEEWEWWWEWWWEWWWWEEWWEWEEEWWWWEEEEEEWWWEEEEEWEWEWWEWEEEEEEEWEEWWEWWEEWWEEEEEWWEWEWEEWWEEWEEWEWWWWEEWEWEWEEEEEEEWEW...

output:

800
640000

result:

ok 2 lines

Test #8:

score: 0
Accepted
time: 42ms
memory: 16832kb

input:

100000 500 500
EWWWEWEWEEWWEEEEEWWEWEEWEWWEEWEEEWEWWWWEWEWWWEWWEWEEWWWWWWWEEEEEEEEEWEEEEEEWEWWEEEEEEEWWEEEWWWEEWWEWEEWWEWWWWWWWWEWEEEWEWWWEWEWWEEEEEEEWWEEEWWWEEWWEEEWEWEWEWWWEWWWEEEWEEWWWWEWWEWWEWWEEEEWWEEWEEEEWEEWWEEEEWWWEWWWEWEWWEWWWEWEEEEEWWWEWEWEEEWWWEEEWEWWWEEWEWEEEWWWWEWEEWWEEWEEEWEWEWWEWEWWWE...

output:

1
227098

result:

ok 2 lines

Subtask #2:

score: 6
Accepted

Test #9:

score: 6
Accepted
time: 0ms
memory: 13728kb

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: 0
Accepted
time: 4ms
memory: 13816kb

input:

100000 10 10
NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN...

output:

1
10

result:

ok 2 lines

Test #11:

score: 0
Accepted
time: 16ms
memory: 15804kb

input:

100000 11 11
SWNESSSWNSEWNSNESSNWEWEWNSNNSWSSWSEEWNENWSWNNEWWSWNSESSEWENNESSENEEEESEESEWENEWSNSNNSSNNSWSNNSNESWEWSENNSESEEWWNESSNNWWSNWNNWNWNWWSEENNNWESSWNWNSEWWNWNNWSWSEWSENSNWNWNNEESSSENWWESSWEESWWENSSENWNNEESWENWSSSWEEWNWEWNNENNWSWEWSNNEESESNWNSEEENWWESSWEEWWSWESSNNEEWWNSSWSNEWSENSNNSENNSSNSSEEEE...

output:

27
27

result:

ok 2 lines

Test #12:

score: 0
Accepted
time: 4ms
memory: 13724kb

input:

100000 10 10
EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE...

output:

1
16

result:

ok 2 lines

Test #13:

score: 0
Accepted
time: 16ms
memory: 13876kb

input:

100000 1 1
WWSSSWEEEEESSNSSSSENWSESSNSWWSWESWSEEWSNSSEESSWESNNNENENWEENSSSSSNENESEESEWWSNNWSEWSWNWESSWNWSEESNSWSWENWEWNWESEWSSNSWENEWNNSWEEWWSSSWNSNWWWNSSWSSNSENESENNNENWESSENNEWENWEENWNWSSSWWWSNWESWEESNNNESNNEESNEWSSNNSSWSSESNSNNWENENEWWWSEESNWEWWNWNNSSNEEWSWNSWEESNSNSNEWNNWWWWSSWSWWESWWENSENWNWNWN...

output:

1
1

result:

ok 2 lines

Test #14:

score: 0
Accepted
time: 12ms
memory: 13780kb

input:

100000 50 50
ENWNNWEESNSNSSESSWNEWWESNWEENNEEWWEWNNESSSEWSWNWEWSSNEEWNSEWSSWNESWSWESEWWSENEWESEWSWSNNWWESSSWSSSESESNSSNESSSWSNWSSSENSWWNWNWNNNSNSNSEENWESENEENNESENSENNWEEESENWSESWSNWNNNSNSNWWENWEEEWSNWWEWSWNSEEEWEWWNSWNNNWWENSNSWWSNNWESNSSSWWNSEWSNWNEEESSEWEESENEESWSNNWSNESEESWEESNWSEEWWSSWESENESSSE...

output:

2500
2500

result:

ok 2 lines

Test #15:

score: 0
Accepted
time: 2ms
memory: 14016kb

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: 0
Accepted
time: 16ms
memory: 15928kb

input:

100000 50 2
ESNNNSWNNESEWSWWWSENWENSWSNSENSWSENWWNEENNWWNESWNWSEWSWWNSSWSSNENSWWWEEEEENSNWWNNESEWSSNSEEENWWNWWNEENSENWSWEWWNNWWNESSSNWNWWSEWEESESNEEEWNNWWEEEESWSEWWNNSNENWWSEEWNWSNWWEEWNSNWWWWWNWWNNSENNEWSEWENSSSSNWSSSNWSNSNEWESEESWWSEEWWWNWWNESNSNSSNEEWSSENNNEEENSNEEEESNSWNNESEENNEESNSSWENSWSWSNSEE...

output:

46
46

result:

ok 2 lines

Test #17:

score: 0
Accepted
time: 0ms
memory: 15992kb

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: 0
Accepted
time: 0ms
memory: 13880kb

input:

100000 10 10
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS...

output:

1
10

result:

ok 2 lines

Test #19:

score: 0
Accepted
time: 2ms
memory: 13988kb

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: 0
Accepted
time: 0ms
memory: 13880kb

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: 0
Accepted
time: 14ms
memory: 13768kb

input:

100000 50 50
WWSNNSSSSSSSWWWSWSNNNNSSNNSSNWWNSSNNNSSSSWSWWSNNSNWSNWNWNWSSWWNWWNNSWWSSSWSNWNWSWWNNNNWSSSNSSNNNSSSNSWSWSWWWWSSNNNSWNSNSSSWSWNNWNSNNWSNWSSSWSWWSWNWSWWNNNSSWWSNWSWSNWNNWNSNSSSNNNNWNSWWWNNSWNWWNNSWWNNWNWSNSSWNWNWWWSNSWSNWNSWSWSNWNNNWNSNSSWWNSNWSWNWNSWNNSSWNSNNWSNSWWWWSSWSNNNNSSWWWWNSWNWSW...

output:

50
50

result:

ok 2 lines

Test #22:

score: 0
Accepted
time: 17ms
memory: 15884kb

input:

100000 50 50
SWSSSNWSNWNNNSNSSSNNSWNNWNWWNSNNNSNNWNNSNWNWSNSWWNSWWNSSWNWNWSWNNSSNNWSWSNNNNWWSNSSSSWSSWWSNNWWSNNWSSSSSSWNNWSWWSWWWWNSNSNWWWSSWWNNSSWSNWNSNSNNSWSWWWNSWWNSNSSNSWSNNSWNWSSNWWSSSNWNWSWSNSNSSWWNNWWWWNNNSWWWNWWNSWWNNWSNNSNNWNSSNWWNNSSNSSNSSSNWSNSSWWWNNNSSWSWNNSNSNWSNSNSSWSSSSWSWNNNNWSWWSNNW...

output:

1
3

result:

ok 2 lines

Test #23:

score: 0
Accepted
time: 17ms
memory: 14044kb

input:

100000 50 50
NNEENENWWNWNNEEWNNWWWWNENNWWNENWNNWNNWWENEENNNEEEWENEENENWNEEEENNEWEWEWNNWNNNEWNWEWNNENWWWWWEENNNNENWWWNENNENENWENNWNWEEEEEWNWWWEWWEWENEENNWEEWWWEEENWNNEENEEEEEWWWWEEEEWWWEEEEWWNNNNEEEWNEWEWENEWEWNEEWNWENWNWEWENNENNWNWEWWENNEWNNNNNNNENNENNNNWEENNNWWWWNNENEEEWNWNWEWNNWNNENWWWWNWNEENWWWEN...

output:

50
50

result:

ok 2 lines

Test #24:

score: 0
Accepted
time: 17ms
memory: 13828kb

input:

100000 50 50
SESWSSWEWEWSWESWEEEWESESSEWEWWSEEEWSESEWSESWWSWEWSSSWSEWESSWSSWSWWWWESEEWEWEWEEEWEEEWWSEEESSEESEEWSESSWEEEWWWSEWSWWSEWSWWEESSWSEEEEEWSSWEWEEESEEWSSWSEWESEWSSEWWSWEWSWESESEEWEEEWESWEESWSESWWSWSWEWESWESEESESSWSESESESSEEWWSSWESEWSWSSSEWWWWSSESSSEESSWWWSEWSSSSESWSSSSEESWSSEWSSSEEESWESWSEEWE...

output:

1
37

result:

ok 2 lines

Test #25:

score: 0
Accepted
time: 6ms
memory: 13832kb

input:

50000 50 49
SNNWEENNESEEEWSESNWSENSSWNWWENENWWEWSEWEEENSNSWEEEESENEEENNSSSESSNEEWSWEWWNSSWNNNSNNNWSSSNEWSSSESWSSWNSSESSNESESWESSWWSEENWENWWENWEWWNNWNWNWEESSSEWWSSSWNSEESWEENNENWEWNNEESSNWSNWSWWWSENWSESSNNNSESNESNSNSWSSNNSNWWEEESESSNNESSWNEENWEESESWSNWNENWNENEEENNSEEESEWENSESWENENSENSWNEEEEWNNSWNNSNN...

output:

3
915

result:

ok 2 lines

Test #26:

score: 0
Accepted
time: 0ms
memory: 13820kb

input:

2000 50 50
NNWSNWWSWNNSNWNNNENWNSWSENSWWSNWNWSSSWNESNSWSENWSNWWSWWENWSWNENWSWENSSSSWNWSNWESWNSNWESSEEEEEESNWNNESENNWNNESNSWNNNNESSWNNENEWSNESSNWNNENEEWWEWNEWNSSWSSSEWEESSNEWSEWNSSSWWSNEWEEWESENNSNSNWSWWENNWNSWSWNESEWNEWESWESSESWNEWNESNNWESSSSENSSSESNWNSNWSNNSESESSSNWNEEWNWSNNWEEWSEWEENSNWSESSESEWENN...

output:

50
1400

result:

ok 2 lines

Test #27:

score: 0
Accepted
time: 17ms
memory: 15796kb

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: 61ms
memory: 17316kb

input:

100000 800 800
SSENEWWEWNSESESSNSEESSEEWESWESNNWWNSEWENENSSEEWESNWSNENSSSNNWNENENSNWWNENESNWNEWSEWNENNWWWNSSSWENNWWEWSSWNNSSSNNNESEENWWNWSSWNEWSWNSSWEESESWESWSENNNSWNNWNENNWWWWSEWNEWWEWNESNSNSWWSEEESWWWWSNNNEEWNWWEWENSSNNNSSEWWSWENENNNSWESWEEEWWEEENSSSSNEEWNNNWWWWSEEWNWNENSEWEWNEWSESNEWNNENSNWEWNNSN...

output:

640000
640000

result:

ok 2 lines

Test #29:

score: 0
Accepted
time: 24ms
memory: 17284kb

input:

100000 800 800
NNSWSNENNEWNWWWWEWNWWSNEWWWNSNEWEWSEWWSEESEEWENESSWWSWSSNEESENWENNESWNESSSENWSWWNWNSNSSNWSNEWWSENNWWEWNEWEWNNNNEWSNEESESWEESNSWNEWWWWNWWESNWNNESNEWWEENWSSENSSWNEENESSWNSESESWSSSEWSWSWWNEWWSSWNNWEWNENWNESWNESNSWENWSSNNWSNWNSESWNWNEESWNEWWENEWWNSEEEWWSSWNSSESWNENSWSSNWEENNWWENENNSNWENWW...

output:

1
3

result:

ok 2 lines

Test #30:

score: 0
Accepted
time: 30ms
memory: 18012kb

input:

100000 800 800
NWWWNWENNENNNWWEWWWWNEWWEWWWEWENEWNWNNNEWENEWWNWWNEENNWWWENEENNENEENWWNNEWWEEWNWEENEWWENWNENEEWWNENWEEWWNWWWNWENNEEEEEWWWNENEWEEEEENNNWNEENNWNNWNEWWEEENENENNWEWNNWNWNNNEEWEWEEEENEWWENENNENNWWENWNNEWNNEENWEEENENWNWENNWNWWEEENWEEEWNENEWNNNWNEENNNWNEWNNWNEWNNENWNEWNEWNNWWENENWENWENWWEEWE...

output:

800
800

result:

ok 2 lines

Test #31:

score: 0
Accepted
time: 52ms
memory: 18208kb

input:

100000 779 785
NWNNNNWSENEWWNENWSSESSNWSNWWNEWNSWNNEWSWNNEEWWSWNSWWEESWENNWWSSWNNSWSSEENSEWWNNWSSSWNNEESNWWSWWWNEENESWNNENWESNWWWEWSNNSENNEESNSSSESWWWWSESNNWWENNWEWNSEESWESSSSNNSNSWSNNWEEEWNENWWNSNSWWWENNSSWSEWWNNEENWWEEEEEEWWWSNENSWSESNWSNNWSSNESWNWSNEENWSSNENEWWWSSSEWNNNESEESEWSWSWSSWNWWNEEWNNSWWE...

output:

28
2100

result:

ok 2 lines

Test #32:

score: 0
Accepted
time: 37ms
memory: 17480kb

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: 0
Accepted
time: 45ms
memory: 17840kb

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: 0
Accepted
time: 75ms
memory: 18072kb

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: 0
Accepted
time: 38ms
memory: 17700kb

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: 0
Accepted
time: 101ms
memory: 17984kb

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: 0
Accepted
time: 67ms
memory: 17416kb

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: 0
Accepted
time: 34ms
memory: 17308kb

input:

800 800 800
NSNSNENNNNEWSNNENNSSSEWWSNESEENSWWENNNENEWNSNSNWESEWWESENESWWSWENEWWWWSESSENEWSSSWNSEWWNNWSEESSNNNWEEWEENESESSWENNNSENNEWWNWNEEWSSNNWSSNEWEESSNWWWNESNWSESWSSNENSNSWSSWESNNWNESSESWWSWSNWEEWENNNNENNEWWENEENNSWSNNNSWEEESSNSNSWSNSWENSEWSESENWSEWNNENWWWSNESNWSEWSSSWWENNNNSSSNNENEWWNEEEEESSNEW...

output:

635256
635256

result:

ok 2 lines

Test #39:

score: 0
Accepted
time: 63ms
memory: 17364kb

input:

100000 800 800
WSENNSNEESNNWNEENNSSSSSNWESSSSWEEWNENSNSWSWNNSSSSNSSWNEWESNNESEWESESWWSENEWNWEEEWESNWSWNNSENEEWENNSSWENESNEEENESSWESNNWESENWWENNWNESWSSEWNWENEWENSNWNWNESEWSNNNWNSSEWNNSWWSESENNSSEEWENWWWEWWSNSEEWESSNESESWWNWWESNSESEWSWNNNEWWNWWEEWWSNNWESWNENSEWSWWNSENWEWSEENEESNNEWWNNNNEEWESESNNSSWEEN...

output:

2
210940

result:

ok 2 lines

Test #40:

score: 0
Accepted
time: 82ms
memory: 17484kb

input:

100000 800 800
NEWNNNSEWNEWNEWWSWSWNNNWWNSESWEWSEWNNSWWNSWWEWWWNSSSWWWNNWWWWSEESNENWEEWNNWNNESEENSNEENSNENWSNENNENEWWWSESSESNESEEEESNEWWSSNEWENWNNENNWSSWENENESNEEEWWEEESNSESSEWWSEWSNSNWWESWWNSSSSWNWEWWSNWSSNNNSNWENWEESWNNNNEWNSWWWSWSWSNNSWNEWEEESNWENSWSWSWSEWSNNNWNNNEEWWWSWNWWWSSWSSSNEWSSEWEWSEWNSES...

output:

4
251772

result:

ok 2 lines

Test #41:

score: 0
Accepted
time: 28ms
memory: 17340kb

input:

50000 800 800
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS...

output:

1
53315

result:

ok 2 lines

Test #42:

score: 0
Accepted
time: 92ms
memory: 17840kb

input:

100000 800 749
EWNSSNSNESNNSNSNEWEWSSEWWENWWESNNENWESESSNESEEWWSSSWEESWSESEWENEEWSNNWEENNESESSWNNESSENEENEEENSEEEESWNSSSWSSESNWNWESWNWENNEWNWWSNSWNSSWNNSNSESNESWSNSSWEESSNWSWWSEWNWWENWWNNESSWNSNSWEWNNWNNWSNNEWEWNSSNSSENWWESNSSSNWENNWNEWNESSESSNWNESWWNNSSEWSWWWSENNNNEWSNESENNEENENWSWWSEWSEWSNSNNWEESE...

output:

1
1767

result:

ok 2 lines

Test #43:

score: 0
Accepted
time: 40ms
memory: 17936kb

input:

100000 800 800
SNSWWNNSSSWNWNNNSSWWWNSSWWSWWWWWWWSSNNNSWNNSNNSWNSNWNNSSWWSWSWWNSNWNSWNSSNSWWWNSSWWSSSWWSNNNNSNNNWSSWNWNSSSSNSNWSSNSSSSNSSWSSWWWNSNWNNSSNSNNNWNSNNWWNNNNWWSNWSSWSSWWNSSSWSWSWWSSSNNSNNNNWSWWSSNWSSSNWWWWNNWWSSWWNWNSNSWSNSWWWWNWWSNNNNWWSWWNWNSWWNNSNSWNNNSWWSNNNNNSWWWNSSNSNNWNNWNNSNSWSNWWW...

output:

1
1054

result:

ok 2 lines

Test #44:

score: 0
Accepted
time: 47ms
memory: 17296kb

input:

100000 500 500
SSENEWWEWNSESESSNSEESSEEWESWESNNWWNSEWENENSSEEWESNWSNENSSSNNWNENENSNWWNENESNWNEWSEWNENNWWWNSSSWENNWWEWSSWNNSSSNNNESEENWWNWSSWNEWSWNSSWEESESWESWSENNNSWNNWNENNWWWWSEWNEWWEWNESNSNSWWSEEESWWWWSNNNEEWNWWEWENSSNNNSSEWWSWENENNNSWESWEEEWWEEENSSSSNEEWNNNWWWWSEEWNWNENSEWEWNEWSESNEWNNENSNWEWNNSN...

output:

1
227231

result:

ok 2 lines