QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #525090 | #1826. The Paladin | RngBased# | AC ✓ | 0ms | 3840kb | C++17 | 1.2kb | 2024-08-20 12:34:47 | 2024-08-20 12:34:47 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
#define all(x) x.begin(), x.end()
using namespace std;
const int INF = 1'000'000;
int N, K, cost[26][26], dp[26][105];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> N >> K;
for (int i = 0; i < 26; i++)
for (int j = 0; j < 26; j++)
cost[i][j] = INF;
for (int i = 1; i <= N; i++)
{
string s;
int c;
cin >> s >> c;
cost[s[0] - 'a'][s[1] - 'a'] = c;
}
for (int i = 0; i < 26; i++)
for (int k = 1; k <= K; k++)
{
if (k == 1)
dp[i][k] = 0;
else if (k == 2)
dp[i][k] = cost[i][i];
else
dp[i][k] = INF;
}
for (int j = 1; j + 2 <= K; j++)
for (int i = 0; i < 26; i++)
for (int k = 0; k < 26; k++)
dp[k][j + 2] = min(dp[k][j + 2], dp[i][j] + cost[k][i] + cost[i][k]);
int ans = INF;
for (int i = 0; i < 26; i++)
ans = min(ans, dp[i][K]);
cout << (ans >= INF ? -1 : ans) << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3520kb
input:
5 9 ab 4 ba 1 bd 3 db 100 bc 4
output:
20
result:
ok answer is '20'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
1 100 aa 100
output:
9900
result:
ok answer is '9900'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
676 100 aa 36 ab 55 ac 2 ad 75 ae 47 af 82 ag 55 ah 31 ai 40 aj 55 ak 27 al 84 am 93 an 4 ao 26 ap 70 aq 77 ar 100 as 13 at 97 au 97 av 42 aw 60 ax 3 ay 64 az 46 ba 72 bb 37 bc 35 bd 66 be 73 bf 67 bg 36 bh 62 bi 38 bj 45 bk 50 bl 10 bm 6 bn 43 bo 26 bp 3 bq 55 br 11 bs 94 bt 78 bu 78 bv 58 bw 12 bx...
output:
396
result:
ok answer is '396'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
676 100 aa 2 ab 79 ac 80 ad 60 ae 64 af 37 ag 26 ah 70 ai 49 aj 18 ak 63 al 75 am 51 an 7 ao 62 ap 56 aq 38 ar 40 as 35 at 61 au 59 av 86 aw 41 ax 69 ay 96 az 75 ba 68 bb 97 bc 99 bd 89 be 67 bf 27 bg 67 bh 28 bi 36 bj 5 bk 6 bl 83 bm 6 bn 35 bo 57 bp 51 bq 34 br 78 bs 78 bt 52 bu 79 bv 3 bw 52 bx 2...
output:
198
result:
ok answer is '198'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
676 100 aa 53 ab 91 ac 19 ad 42 ae 63 af 76 ag 4 ah 48 ai 71 aj 97 ak 51 al 90 am 14 an 3 ao 82 ap 39 aq 69 ar 93 as 89 at 57 au 16 av 10 aw 6 ax 96 ay 87 az 60 ba 62 bb 21 bc 27 bd 81 be 60 bf 75 bg 66 bh 16 bi 47 bj 32 bk 85 bl 24 bm 76 bn 9 bo 38 bp 46 bq 69 br 24 bs 2 bt 84 bu 34 bv 30 bw 61 bx ...
output:
198
result:
ok answer is '198'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
5 100 ab 100 bc 100 cd 100 de 100 ef 100
output:
-1
result:
ok answer is '-1'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
8 20 ab 8 ba 7 cd 10 dc 11 aa 100 bb 100 cc 15 dd 25
output:
204
result:
ok answer is '204'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
401 6 ol 34 ps 96 du 96 np 31 vc 20 dy 71 lk 62 xu 32 fn 2 mb 88 da 12 uy 25 pe 20 ms 96 wm 41 ed 67 bx 57 sb 20 de 3 ul 14 sm 14 tt 42 rw 34 ai 61 fh 65 im 34 cl 26 su 97 fj 80 xb 49 ew 98 vs 30 ls 77 pw 35 pv 51 yt 78 rv 91 st 98 cr 98 jg 1 nx 88 dj 68 ma 17 ay 9 hz 28 dx 85 gn 74 kb 56 nn 96 qn 1...
output:
20
result:
ok answer is '20'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
467 68 rq 42 ot 90 lf 36 gp 58 da 64 ve 53 mj 5 rk 37 hj 97 ro 31 dz 44 vz 69 xm 37 hq 77 zd 53 mm 78 aj 47 pj 9 jq 70 li 75 od 100 hx 47 or 53 kb 18 md 90 un 23 ef 27 gy 58 dl 22 ja 57 wf 90 gn 76 su 53 uh 75 ff 45 el 6 le 54 kh 88 pw 90 cv 90 sw 82 ka 85 gf 62 ma 93 tl 82 mf 25 ek 74 wh 31 qe 7 gc...
output:
454
result:
ok answer is '454'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
492 2 to 6 he 82 zy 44 jv 98 pq 4 zz 82 tx 82 tp 89 jw 33 tt 95 hf 62 gp 19 ox 28 em 11 ir 24 ou 79 jp 78 ny 17 fc 39 iv 23 qu 10 od 72 dr 16 gk 24 yc 2 nz 32 op 11 ys 35 qt 15 ip 51 gb 83 ob 4 xp 59 ic 56 gh 66 gm 27 oa 35 sj 82 lk 25 rp 53 ws 4 zm 76 tl 39 mt 31 oq 98 zx 52 ua 61 py 41 ii 74 ni 77...
output:
9
result:
ok answer is '9'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3492kb
input:
94 90 iy 28 kc 65 vf 59 by 89 lo 46 qu 14 nx 73 xh 27 mr 31 lv 49 nl 62 wg 2 dn 55 ch 4 kg 83 he 53 ed 7 yj 26 pj 6 pz 68 jr 46 uk 35 xq 77 xx 58 ro 48 uz 41 ng 31 yn 59 mh 24 df 99 qj 67 gn 55 ou 18 rp 58 tk 48 ez 11 yh 74 qg 50 od 23 md 54 ak 60 dk 80 sy 96 bo 3 bf 4 hb 43 do 48 du 38 fs 78 rl 60 ...
output:
2136
result:
ok answer is '2136'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
28 68 qw 31 gx 35 xg 50 iv 17 yc 95 yd 43 kq 84 em 16 qr 43 zl 27 vr 75 bp 71 vz 75 il 65 br 82 ej 72 xb 73 mr 28 nu 31 ni 39 ck 31 te 17 rs 27 bc 56 uj 18 rv 28 nm 97 lu 12
output:
-1
result:
ok answer is '-1'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
107 94 ce 38 lx 49 ge 13 fh 25 zd 2 xs 93 su 25 ki 9 nh 82 wd 17 ut 77 kf 18 fi 53 gg 23 dp 69 nm 46 sw 48 re 70 vx 17 ew 91 uv 11 xc 62 ur 86 fx 54 fw 96 qe 32 th 73 if 3 rc 70 sg 5 nj 20 ov 5 qt 77 oi 11 kl 61 qs 92 xv 8 zz 69 ig 44 cm 68 yu 20 ii 79 vn 85 an 80 cv 20 sy 83 eu 92 dn 67 nc 67 rg 23...
output:
2139
result:
ok answer is '2139'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
163 87 fy 52 zq 46 kh 72 uv 16 vo 82 rn 91 np 10 ld 61 ss 48 sj 40 po 49 of 92 uj 25 jw 11 mo 3 oz 25 be 78 lf 8 xy 68 ph 11 dr 84 ol 75 fi 42 sf 41 si 16 zi 35 bl 9 qw 72 xu 37 xm 32 pq 55 ee 5 jc 98 tv 15 rb 31 fl 48 kx 61 jo 27 hi 97 ku 24 co 50 hn 45 eq 58 tz 55 je 49 ww 25 zg 14 vq 70 io 69 lb ...
output:
430
result:
ok answer is '430'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3488kb
input:
435 21 yy 96 ah 78 nh 66 rb 23 hd 48 wi 88 yc 71 kd 7 tt 41 um 84 ki 37 ql 36 xl 88 uy 60 mq 85 mm 93 jn 42 pr 32 qj 69 kw 44 gp 85 lc 31 tg 45 xe 5 zg 26 bq 36 he 61 sk 22 jv 10 ln 14 zs 10 vn 3 va 36 zo 36 nf 56 af 95 ez 46 oy 89 ud 9 ol 100 sb 40 hx 28 zc 46 ad 35 xy 63 ia 56 fv 26 qp 65 zp 63 sw...
output:
20
result:
ok answer is '20'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
123 9 bm 97 pb 79 cv 96 qe 40 bq 7 ay 44 rn 98 mi 39 qz 34 yq 67 el 40 sr 56 wu 5 sf 14 vy 17 ic 99 dx 64 ee 43 oh 59 dd 45 fq 50 oj 32 oz 21 wd 90 ck 39 kl 67 zh 17 le 61 kr 98 xo 17 hm 75 po 56 fj 98 kf 28 fx 15 vl 9 ov 87 zi 99 mh 21 wq 93 dk 34 ad 9 aq 1 ua 83 cu 62 je 47 cl 26 iq 85 rg 86 up 61...
output:
24
result:
ok answer is '24'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3492kb
input:
209 99 my 54 dw 5 rm 19 to 27 rq 26 ti 85 wx 1 nc 24 km 7 sg 90 xj 86 zv 7 ki 94 ca 29 ub 20 wp 20 ib 84 nk 17 cb 89 cz 51 ie 90 hn 16 ty 79 nz 32 lb 41 qg 11 ba 63 fc 43 xo 83 wy 80 pl 50 uc 55 xc 90 jt 83 vo 75 yk 47 jb 98 is 49 zg 15 oe 68 qn 100 cg 82 ps 14 yv 96 iy 43 hx 91 oj 87 ws 54 zy 64 pm...
output:
882
result:
ok answer is '882'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
676 100 aa 49 ab 56 ac 42 ad 37 ae 48 af 87 ag 83 ah 25 ai 18 aj 4 ak 53 al 74 am 6 an 53 ao 53 ap 56 aq 38 ar 32 as 73 at 13 au 49 av 51 aw 14 ax 90 ay 90 az 77 ba 24 bb 28 bc 20 bd 10 be 43 bf 30 bg 41 bh 47 bi 31 bj 45 bk 1 bl 76 bm 25 bn 56 bo 51 bp 23 bq 89 br 35 bs 31 bt 55 bu 20 bv 96 bw 10 b...
output:
99
result:
ok answer is '99'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
676 100 aa 100 ab 100 ac 100 ad 100 ae 100 af 100 ag 100 ah 100 ai 100 aj 100 ak 100 al 100 am 100 an 100 ao 100 ap 100 aq 100 ar 100 as 100 at 100 au 100 av 100 aw 100 ax 100 ay 100 az 100 ba 100 bb 100 bc 100 bd 100 be 100 bf 100 bg 100 bh 100 bi 100 bj 100 bk 100 bl 100 bm 100 bn 100 bo 100 bp 10...
output:
9900
result:
ok answer is '9900'