QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#699189#2957. Tomb Haternickbelov#AC ✓25ms62988kbC++204.5kb2024-11-02 03:58:172024-11-02 03:58:18

Judging History

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

  • [2024-11-02 03:58:18]
  • 评测
  • 测评结果:AC
  • 用时:25ms
  • 内存:62988kb
  • [2024-11-02 03:58:17]
  • 提交

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T>
ostream_iterator<T> oit(const string &s = " "){ return ostream_iterator<T>(cout,s.c_str()); }
inline auto rep(int l, int r) { return views::iota(min(l, r), r); }
inline auto rep(int n) { return rep(0, n); }
inline auto rep1(int l, int r) { return rep(l, r + 1); }
inline auto rep1(int n) { return rep(1, n + 1); }
inline auto per(int l, int r) { return rep(l, r) | views::reverse; }
inline auto per(int n) { return per(0, n); }
inline auto per1(int l, int r) { return per(l, r + 1); }
inline auto per1(int n) { return per(1, n + 1); }
#define A(a) begin(a),end(a)
inline auto len = ranges::ssize;

struct chash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
template<typename T, typename U> using pb_map = gp_hash_table<T, U, chash>;
template<typename T> using pb_set = gp_hash_table<T, null_type, chash>;
#define K first
#define V second

using ll = long long;
using ld = long double;

using vi = vector<int>;
using vii = vector<vector<int>>;
typedef vector<ll> vll;
using pll = pair<ll,ll>;
using pii = pair<int,int>;

constexpr ll NN = 2e5, M = 1000000007, L = 20;

ll f1[NN], f2[NN];
ll inv(ll a, ll b=M) { return 1 < a ? b - inv(b % a, a) * b / a : 1; } // inv a mod b
ll choose(ll n, ll k) { return f1[n] * f2[k] % M * f2[n - k] % M; } // n choose k

int dp[52][52][52][52][2];

void run()
{
    memset(dp, 0x3f, sizeof(dp));
    int m, n, k;
    cin>>m>>n>>k;

    vector<string> a(m, string(n, ' '));
    for (auto &x : a) for (auto &x : x) cin >> x;
    vector<string> words(k);
    for (auto &x : words) cin >> x;

    for (int j = 1; j <= n; j++) {
        dp[0][j][0][(int)words[0].size() - 1][0] = 0;
        dp[0][j][0][(int)words[0].size() - 1][1] = 0;
    }

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            int minw = 1e9;
            for (int w = 0; w < k; w++) {
                int l = words[w].size();
                minw = min({
                    minw,
                    dp[i-1][j][w][l - 1][0],
                    dp[i-1][j][w][l - 1][1],
                    dp[i][j-1][w][l - 1][0]
                });
            }
            for (int w = 0; w < k; w++) {
                if (a[i-1][j-1] == words[w][0])
                    dp[i][j][w][0][0] = minw + 1;
                for (int l = 1; l < (int)words[w].size(); l++) {
                    if (a[i-1][j-1] != words[w][l]) continue;
                    dp[i][j][w][l][0] = min({
                        dp[i-1][j][w][l - 1][0],
                        dp[i-1][j][w][l - 1][1],
                        dp[i][j-1][w][l - 1][0]
                    }) + 1;
                }
            }
        }
        for (int j = n; j >= 1; j--) {
            int minw = 1e9;
            for (int w = 0; w < k; w++) {
                int l = words[w].size();
                minw = min({
                    minw,
                    dp[i-1][j][w][l - 1][0],
                    dp[i-1][j][w][l - 1][1],
                    dp[i][j+1][w][l - 1][1]
                });
            }
            for (int w = 0; w < k; w++) {
                if (a[i-1][j-1] == words[w][0])
                    dp[i][j][w][0][1] = minw + 1;
                for (int l = 1; l < (int)words[w].size(); l++) {
                    if (a[i-1][j-1] != words[w][l]) continue;
                    dp[i][j][w][l][1] = min({
                        dp[i-1][j][w][l - 1][0],
                        dp[i-1][j][w][l - 1][1],
                        dp[i][j+1][w][l - 1][1]
                    }) + 1;
                }
            }
        }
    }
    int ans = 1e9;
    for (int j = 1; j <= n; j++) {
        for (int w = 0; w < k; w++) {
            ans = min({ans, dp[m][j][w][(int)words[w].size()-1][0], dp[m][j][w][(int)words[w].size()-1][1]});
        }
    }
    if (ans >= 1e9)
        cout << "impossible";
    else
    cout << ans;
}

int main()
{
    //KING OF THE WORLD...... U.W.T.B
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    run();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 61800kb

input:

3 4 1
X X P X
X X A T
X X X H
PATH

output:

4

result:

ok single line: '4'

Test #2:

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

input:

5 5 2
X X P X X
X X A T X
X X H H X
X M O X X
X E X X X
HOME
PATH

output:

8

result:

ok single line: '8'

Test #3:

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

input:

5 5 2
X X P X X
X X A T X
X X H X X
X M O X X
X E X X X
HOME
PATH

output:

impossible

result:

ok single line: 'impossible'

Test #4:

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

input:

4 4 4
X A X X
X B C X
X D D X
F E E F
ABC
DEF
AB
DEF

output:

5

result:

ok single line: '5'

Test #5:

score: 0
Accepted
time: 11ms
memory: 62028kb

input:

30 30 50
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A...

output:

30

result:

ok single line: '30'

Test #6:

score: 0
Accepted
time: 11ms
memory: 62324kb

input:

40 40 50
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A...

output:

40

result:

ok single line: '40'

Test #7:

score: 0
Accepted
time: 25ms
memory: 61600kb

input:

50 50 50
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A...

output:

50

result:

ok single line: '50'

Test #8:

score: 0
Accepted
time: 10ms
memory: 62356kb

input:

5 4 2
X X X X
X A B X
X X C X
X E D X
X X F X
ABCD
EDF

output:

impossible

result:

ok single line: 'impossible'

Test #9:

score: 0
Accepted
time: 9ms
memory: 61536kb

input:

4 4 2
X A B X
X X C X
X E D E
X X F X
ABCDE
EDF

output:

impossible

result:

ok single line: 'impossible'

Test #10:

score: 0
Accepted
time: 3ms
memory: 62636kb

input:

4 7 2
X A B X X A B
X X C X X D C
X E D E X E E
X X F X X D F
ABCDE
EDF

output:

impossible

result:

ok single line: 'impossible'

Test #11:

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

input:

4 7 2
X A B X X A B
X X C X X D C
X E D E X E E
X X F X X F D
ABCDE
EDF

output:

8

result:

ok single line: '8'

Test #12:

score: 0
Accepted
time: 3ms
memory: 61380kb

input:

4 3 2
X A X
X B X
X C X
X D X
ABC
ABCDE

output:

impossible

result:

ok single line: 'impossible'

Test #13:

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

input:

4 5 2
X A X X A
X B X C B
X C X A B
X D X X C
ABC
ABCDE

output:

6

result:

ok single line: '6'

Test #14:

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

input:

5 6 3
X D X X X X
X A C E X A
X B B F C B
X C A G H B
X D X C I X
ABC
ABCDE
EFGHI

output:

impossible

result:

ok single line: 'impossible'

Test #15:

score: 0
Accepted
time: 7ms
memory: 60652kb

input:

5 6 4
X D X X X X
X A C E X A
X B B F C B
X C A G H B
X D X C I X
ABC
ABCDE
EFGHI
DACEFBBCAGHI

output:

12

result:

ok single line: '12'

Test #16:

score: 0
Accepted
time: 3ms
memory: 62988kb

input:

5 6 8
X D X X X X
X A C E X A
X B B F C B
X C A G H B
X D X C I X
ABC
ABCDE
EFGHI
DACEFBBCAGHI
A
B
C
D

output:

5

result:

ok single line: '5'

Test #17:

score: 0
Accepted
time: 3ms
memory: 62776kb

input:

5 6 10
X D X X X X
X A C E X A
X B B F C B
X C A G H B
X D X C I X
ABCDE
EFGHI
DACEFBBCAGHI
A
C
D
E
F
G
H

output:

7

result:

ok single line: '7'

Test #18:

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

input:

2 4 2
X A B C
D E F X
ABC
DEF

output:

impossible

result:

ok single line: 'impossible'

Test #19:

score: 0
Accepted
time: 11ms
memory: 61580kb

input:

2 4 2
X A B C
X F E D
ABC
DEF

output:

6

result:

ok single line: '6'

Test #20:

score: 0
Accepted
time: 7ms
memory: 61784kb

input:

3 5 3
X D A X X
D X A B C
E F X D X
ABC
DEF
A

output:

impossible

result:

ok single line: 'impossible'

Test #21:

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

input:

10 5 9
A E F G X
B E F G H
C L K J I
A M X X X
B N X X X
C O X X X
A P Q R A
B Q R A B
C A B C B
X X X A B
ABC
ABBB
ABEF
KLC
KLM
NOPQ
NOPA
RA
BBB

output:

16

result:

ok single line: '16'

Test #22:

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

input:

50 50 2
A B C D E F G H I J K L M N O P Q R S T U V W X Y Y X W V U T S R Q P O N M L K J I H G F E D C B A
A B C D E F G H I J K L M N O P Q R S T U V W X Y Y X W V U T S R Q P O N M L K J I H G F E D C B A
A B C D E F G H I J K L M N O P Q R S T U V W X Y Y X W V U T S R Q P O N M L K J I H G F E ...

output:

1250

result:

ok single line: '1250'

Test #23:

score: 0
Accepted
time: 3ms
memory: 60756kb

input:

10 10 10
V G V A I A L F E M
N J G S Y G K C D I
P E D E X A K O U P
D Y B V Q T V X U Y
O B E D P B V B F C
B S Y E N Q O S K O
P B E Y T N H F S V
Q E Q S F S X U N M
V D M P A L S Q V H
L U H O K N O S P I
LKC
OXB
FKS
FUQ
SLN
IYG
KKA
XQP
DEY
EBP

output:

15

result:

ok single line: '15'

Test #24:

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

input:

10 10 10
F C Y O E B Z T N P
V E Q M X G G N V M
W X Q V W G N N H U
O V N K Q X U B Y S
R F J D C T S O Z Y
R Z H C O K W F K W
E S J E L P B K H I
G M Y X W V Z M H X
F B U Y A G D Y B A
C D G P Q W U M Z H
BZG
NVM
UHY
BOS
TCD
COK
PBK
HHM
ZVG
AQ

output:

26

result:

ok single line: '26'

Test #25:

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

input:

10 10 20
D I U R U T M Q H O
Z X Y V C T R A D G
I W U Q V I Q E S I
G H S U O W F N J T
H D R Z G P D T Q C
X Y L R N A Z J W Y
E I E Y J B V W W W
I X Z J Q E O W M U
L Q S L J V J T A P
Y J N P I M V R M F
DIX
WHD
HXY
LEZ
SLP
URU
TMR
TCV
OWF
NTJ
WWW
UPF
QAE
QFD
TQC
YWJ
WWM
UPF
IXW
IGH

output:

12

result:

ok single line: '12'

Test #26:

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

input:

10 10 30
B G H W Z Q H C A F
Y N Z F Q C H T N I
H C I T S C S W X I
O K I B N P H L H O
G S Y J U R U H U Z
G D J I P B V Y C G
E F G A Z J N U H E
O K V S Q Y W S J Q
M I Y A O W I K S B
D K C P Y N M B E C
CAF
INT
WXI
OZU
CGE
QJS
WIK
B
GHW
FZI
IKO
GGD
JIP
BJZ
AGV
SQO
AYC
GNY
HOK
SGG
EFK
IK
ANI
IO...

output:

14

result:

ok single line: '14'

Test #27:

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

input:

10 10 40
Y G T B D M C O T V
W E B S H K U K W K
H J W W R Y W Q B G
T N W I M G L I E I
D J G V H T K U X V
M K H B R F U O I P
H C I D Q S G Q Q N
T X R A R S G P F M
K B D Q S Z H C J P
F I S Q M Q G K W A
BTBW
JNJK
MHTK
BI
YWEB
WJNT
DMHT
KF
CMKU
WQBE
IVPN
QQGG
PCJW
BTGE
BWWR
MHTF
RBHI
RXBD
S
GEB...

output:

14

result:

ok single line: '14'

Test #28:

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

input:

10 10 50
W M Q C R C Q L M V
B Y H B M V G Z D D
T G A R Q B Y G M U
L X C U K F U U O K
V H N R L N X Z O Z
S K L Q R V X S R R
H U D Y Q G B C F A
V G V O M B U Z K J
R P D D D O P Y L E
C O Y Q G G H R K Y
MLQCR
CBHAC
NLQRV
XBCFK
ZUPH
QGYBF
UUZOZ
RAFKJ
EY
RCQLZ
GYUFN
VRQGB
MDG
MDZGU
OOZSC
ZYLK
LQ...

output:

13

result:

ok single line: '13'

Test #29:

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

input:

20 20 20
I I R S P D D Z W Z J T T V L Y E L W I
Z B M I P H A F Z Y W W P H J J S Z S D
W L T R W F U M J T L R S O S P F F R Z
V I I B G I V H U O L Q A Q C C X R E S
A N J M B J Y G P X T X Y P L N L J U W
V N M M Z Q T G I E Y N Z S P D K V I F
J J I W R I J M P H J N B O C I U Q B E
Y U M J G J...

output:

29

result:

ok single line: '29'

Test #30:

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

input:

20 20 20
Q X X N C I P Q T K K C Y C L C R R D V
S J W K L A F F L R D U C W G W R O F H
A V I T G G L X X E M L Q J U C B R S Z
K B W P F N F W R I H O V X A L F Q Q Z
E K F S A T B F D Y X B Z Q F M B O D U
M D U R D G U P I C H F D E D W P M F H
S T E U W Z I N X K M K Q X M Q B I M J
J G Q Z X B...

output:

34

result:

ok single line: '34'

Test #31:

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

input:

20 20 20
B N O C N O H U Z G K T C Z T A S I X G
K L T J I Z I I T K D O Z H F R J G V T
K P Q L C F L S G S G C S N W K B O N S
Y V H B N M Y N D S Y Z U U X B F T C H
I O V G V C E K X M W E J Q I I X J R S
C P G R F A N L F Z A K U O Y I E U T Y
D X P M N R K X S T S I B F J A E N H N
L Q Y A Z D...

output:

34

result:

ok single line: '34'

Test #32:

score: 0
Accepted
time: 3ms
memory: 61844kb

input:

20 20 30
M N X B W N U C I K H U Q P X A X H B I
T N O S X C A T D T E R D X U A K I Q Q
P P L L Y J A R Q F Y H J N E O O P A L
E Z N H Q Q F N S W W Z A Z U F P K R M
P T Z V B D K S J M I I R T Z J M J R D
J Z T O L Z J X K W U N Y L P E T T F Z
R J V R E X U W L F A Y I G D A T A J Z
T V X A Q S...

output:

35

result:

ok single line: '35'

Test #33:

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

input:

20 20 30
H T H H P A C J V A K F Y I R U X O T D
F Q G Q V Z G D Q F E F W Q T S X R Y L
E D A T Q H C L K F L L J U F G O K P W
F O K D F K R V Q S E V Z V N I M R R F
U A E X Q T P E A P H P N T H C F Z U B
O Y P M S P T Q C Q H Z K F E D X L H G
N Q R B K I B V C Y L V H T U Q B K Z I
Z O O D S Y...

output:

36

result:

ok single line: '36'

Test #34:

score: 0
Accepted
time: 7ms
memory: 61416kb

input:

20 20 30
S H Z Y Z J V O C W L W D F C S Y D N O
Y U D P S Y H H Z Y E Z V Z S N P J P X
L Y H J M G E G W T E A M W F Q P H K M
T I X P N J J M C D X G X U L V M U F N
Z C T M J C T L X E G S Z V L W D U L Z
F K Z L W L M M Y O A G E S A O K S W Y
Z U D U B A G G X H R V S Y R X G Q T K
B X X E U A...

output:

31

result:

ok single line: '31'

Test #35:

score: 0
Accepted
time: 8ms
memory: 60896kb

input:

20 20 50
R V F A B T D V Y E X T R M V K E M U D
X I X E T H K R O Z H M P P R V E I N G
X F L P F T M B W D J S W G G R Z B B E
U U K C V A F K U U Y P K L Y S D S Q N
M M K T Y D G H G X X E T U G Z M Z U X
S Y Y P J J E T Z A I Z X D X R T X Z E
X L U W V Z P M R Q Q T F N K Y U W C Z
Q Y V X A X...

output:

32

result:

ok single line: '32'

Test #36:

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

input:

20 20 50
N Z Q G V G O E L U C C Z F Q D F Q K Z
J N P C P G P B E L F B I H O N R S U C
M U A V X Q O U R E W W Z M H J B V Q N
W H I Z M U R U T P G L H H S V B Y S G
R T O W N V L T Z A V L P U N P F O Z T
X W U M P Z P M R V W L I Y M Q V N B L
U S R F B L Z J J J B Q E A C Q C I R F
W R M A F D...

output:

36

result:

ok single line: '36'

Test #37:

score: 0
Accepted
time: 7ms
memory: 62104kb

input:

20 20 50
Y P H X E P E I R O C V C C Z B E H G K
C P M B M F S E L E F U H P M I L J K O
T O I N T P Q P A S P L Z O J T A T L G
L D U L S T K M F A X W F E Q L A C G O
W Y D K I E P A T P V O Z W Q M C J O R
N J G M U V I I P S O Q A K G C L U P B
F W C X T E B W F S I O P F Z Y H N L J
Z A V B F F...

output:

33

result:

ok single line: '33'

Test #38:

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

input:

30 30 50
J L K N B P S W Y S K O O W A C Z T Z O J I W T L L T F Y J
Q T S E M O K O O I W R O N F H N C W M I S H O L O J E L P
Z R Z Q K U G R W O N E N G G O C T B A F W K T G Z Y I Z G
O Y A V Y V G C Y P K O R Y D S R C X J S O L M C Y U B O C
Q Q R N M I B E Q J Z O U R L S S C P V V X F G C L...

output:

56

result:

ok single line: '56'

Test #39:

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

input:

30 30 50
T H K D X P F L I V T J Y Q Z F X E S S N E J M M R V F L P
B T G S J S J U U Z X V R N Q Y L P T I Y A Q M M K P R M X
L G C T B W A W L E D O V I X P F J V J P U S D G U J P D X
F H A W E C L U K O H T C I M P A X E Z U K V R Y W E F O D
D L H E G P A N B C T N Z F W N D R T F P R Q L A R...

output:

51

result:

ok single line: '51'

Test #40:

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

input:

30 30 50
T N I E N I S G B V Z C G Z E Q H R Z M B C M H I T Y T W D
T C L D J R R E F B P T Z J U T V S I K E Z U Y L Z U V X Z
N Y Y Q B K U G Y R F Y Y X R Y T V Z G V J P P R J P L D N
C N G X V S N B Y M O O A Z U K A F V T T M W K T O Q N H Y
A L U I Y A P W F B G M U N B C L O S M N H M B N J...

output:

53

result:

ok single line: '53'

Test #41:

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

input:

40 40 50
D J J U J I G W K Z H X Q T E S F C S Q G W Z Y H B Z S J J E C X R H V Q L J U
Q X D J G M T F F H X H D Y N V B I X H A M C T R N P L P F V G D Z I B W L U S
F H X Z P E Y S J E T W F W D Z S U I K L U N J D H J X D K U K G O Q M C R F Z
M G K Z Q G N E Q U Z L Z Z N X U D W W H C W G J P...

output:

104

result:

ok single line: '104'

Test #42:

score: 0
Accepted
time: 10ms
memory: 62172kb

input:

40 40 50
O F K K E I T K S C Q S C N F V A O L V M P L P G H D T W O P B K E H B P P N N
T A I L R C Q S A B P O K W O O K V Y Q O A H Y H N L Q G V L O L B Y E Z D P B
P H D K P Y H A N X M G G X J I W M U J I Z X V M E S S K B Y G R R M J L Y E A
X B Z P K L O O B M S J E L Z S F R B H D X H L G V...

output:

74

result:

ok single line: '74'

Test #43:

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

input:

40 40 50
N R R M G V D P O L C N N T Y L H X P K N F E F H S E D L P T P F U G J E O L Y
E J M R M R Y M D N T D X F P R U P N I O N V M P E G Q Y N N U V T L B Q B Z Z
C P U S F Z U X W Q A U C W D J G R D I T N W X Y C K X N O G Y I F K N U D J F
W S R S E K X U V U R H R A S T T Y I V S A D E P P...

output:

87

result:

ok single line: '87'

Test #44:

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

input:

50 50 50
A N S C B V O D X P K I Z N X M D I K O T Z R W F Y G C Y V E O S J G N D V Q Q F M S R Y H V Z X H
J L D E O M C D N R C B A R F H A V N B D C D V D E T R U L M O C B D U F E A H U D B X L S L J N G
Q S J I J Z T R V F I W T J G J E J I G H N F J Y R X E H N K I W M E O E N M E N V N J N V...

output:

105

result:

ok single line: '105'

Test #45:

score: 0
Accepted
time: 3ms
memory: 61488kb

input:

50 50 50
K J V Q X X B T E S T B J G Y P Z U D Q X U D P E E H B J A P O G X E R B Z U J I Q X R J A S K U B
C S M C P G J Q N Z Q P E U Y J W A E R T M I X U H V J P U W O I M E O O O E A L M D W Q Z R C A H
N Y T S S W C L D W M S D L C G O N G H U I V A S W V L U E D H B X Q J P B O O J P Y M J C...

output:

113

result:

ok single line: '113'

Test #46:

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

input:

50 50 50
X F W G V Y P H O X B W V C X R V F W V E O Q H D L J B W G A N R J D V A D Y D J T D T V S P X P V
U A U C R C R B N I D E J Z O M R F T F J U Q Z K K A B J G G M Q V E L X W K R E V C Y W I U W K F
K D G E B T N G N L N Q M Q Y E Z U G H F D K Q K C V T F V W F G J C D A S S Z D M I R G I...

output:

107

result:

ok single line: '107'

Test #47:

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

input:

1 1 2
A
A
B

output:

1

result:

ok single line: '1'

Test #48:

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

input:

1 1 2
X
A
B

output:

impossible

result:

ok single line: 'impossible'

Test #49:

score: 0
Accepted
time: 15ms
memory: 61328kb

input:

1 10 3
A B C D E F G H I J
HA
ABD
HGFE

output:

4

result:

ok single line: '4'

Test #50:

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

input:

10 1 3
A
B
C
D
E
F
G
H
I
J
ABC
DEF
HIJ

output:

impossible

result:

ok single line: 'impossible'

Test #51:

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

input:

10 1 3
A
B
C
D
E
F
G
H
I
J
GHIJ
DEF
ABC

output:

10

result:

ok single line: '10'

Test #52:

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

input:

5 5 1
A B C D E
F G H I J
K L M N O
P Q R S T
U V W X Y
ABCDEFGHIJKLMNOPQRSTUVWXY

output:

impossible

result:

ok single line: 'impossible'

Test #53:

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

input:

5 5 1
A B C D E
F G H I J
K L M N O
P Q R S T
U V W X Y
EDCBAFGHIJONMLKPQRSTYXWVU

output:

25

result:

ok single line: '25'

Test #54:

score: 0
Accepted
time: 3ms
memory: 62604kb

input:

5 5 6
A B C D E
F G H I J
K L M N O
P Q R S T
U V W X Y
ABCDE
JIHGF
KLMNO
TSRQP
UVQL
MRW

output:

impossible

result:

ok single line: 'impossible'

Test #55:

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

input:

3 8 1
S X X X X X X S
T A T E S T A T
X X X X X X X E
STATE

output:

10

result:

ok single line: '10'

Test #56:

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

input:

2 4 1
S T A T
X X X E
STATE

output:

5

result:

ok single line: '5'

Test #57:

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

input:

3 3 1
X X S
X A T
X X E
STATE

output:

impossible

result:

ok single line: 'impossible'