QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#687172 | #6466. Concerts | PetroTarnavskyi# | AC ✓ | 47ms | 121548kb | C++23 | 1.1kb | 2024-10-29 17:31:39 | 2024-10-29 17:31:40 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef double db;
const int N = 1e5 + 47;
const int K = 1e3 + 47;
const int mod = 1e9 + 7;
void updAdd(int& a, int b)
{
a += b;
if(a >= mod)
a -= mod;
}
int dp[N * K];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
LL k, n;
cin >> k >> n;
VL h(26);
FOR(i, 0, 26)
cin >> h[i];
string s, t;
cin >> s >> t;
if(n >= N || k >= K)
exit(0);
dp[0] = 1;
FOR(i, 0, n)
{
FOR(j, 0, k + 1)
{
if(j != k && t[i] == s[j])
updAdd(dp[min(n, i + 1 + h[t[i] - 'A']) * (k + 1) + j + 1], dp[i * (k + 1) + j]);
updAdd(dp[(i + 1) * (k + 1) + j], dp[i * (k + 1) + j]);
}
}
cout << dp[n * (k + 1) + k] << "\n";
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3668kb
input:
20 1000 3 8 6 7 7 2 3 0 9 0 3 6 3 5 2 4 5 5 2 6 7 0 9 5 0 1 JWNOUXSQLCNEPZIATFRG VBNTLXRPBHYNSDNNUDOLFJWPHOZVJWERGFCGRQDSOHPSSYXKBLEHYVXOCZHQPIZFQVFEDZJFQPWJOZXYUNWGOBLGHCGDAWTLNPVOHESQFLSIYYSFBRPLCRAVRGTKGTATWBBMRWWHPIYEKYZJSTLZNJAOENGENYCWJSBTZNSVBTJUWHBVRWJXURHVNJCMBQKDGJPURYCDBKESUGJUULYBQTXBOBN...
output:
324855496
result:
ok single line: '324855496'
Test #2:
score: 0
Accepted
time: 0ms
memory: 5588kb
input:
100 5000 21 12 8 29 4 2 0 10 2 8 25 28 21 18 29 24 25 26 11 7 17 14 11 18 8 25 QACFDQHBWAEVSUJFPGLXRBQYAPUGUQKKPEXDKOGLOQKEIVNCIHYTFNVIMJSJUCHESHVZVGWMJISHNCTNEAKWYUUQAGMFYQPSRHDQ VYXPGLMYGFZYBSPWFWVXCNCGMEGQXJOIKFLJEZAKVTFPYXQLXXUMNKAKAJOEFSIBZYWLXSIAMJIYFAVTLZXHOQOHDCJLVEEWJSEDTHYRUHDZNGGHOKZWMCUR...
output:
32963522
result:
ok single line: '32963522'
Test #3:
score: 0
Accepted
time: 0ms
memory: 9508kb
input:
150 10000 16 47 24 35 25 47 14 24 43 35 32 16 10 2 25 45 34 1 29 1 48 6 26 15 21 42 YNIVUSBGIXCPLSHDOOKOEUHCSGYTEKXPJFWAGMQJZTILXRBAVFNWLWNCGRDFDULGMCKFAPXZOKDXDOKQHMWMTKZLBJRXLDUNWVHQLHZDUMYFXLKWWJRISZPMBTEXUAVXNJMHPHIJTBQJEIISXVFOSO ZBNWNVOGYUDWAAIQYSJGQGQWMJOYBAXUMMQXJCPWBQGGNDVDBEYFEKTNPGRYLUDNR...
output:
975730909
result:
ok single line: '975730909'
Test #4:
score: 0
Accepted
time: 16ms
memory: 42972kb
input:
200 50000 92 55 67 34 6 14 96 73 82 87 45 94 11 18 35 80 14 73 84 32 44 9 95 37 50 42 JYSXZIQYKUUQNNMKUPEZBKYYIQIWRYUTVSECDODULYVDQBPCQYOXUKKHQWQUDVFOEYAECSLQBULKNNVKYPZHCYYRHJOUEYLBWLWEHTZHDVYTCXCXQFYNPUIKOWDZLPLBAPFWPXCUBFPDIPUXISNYEFMATHLIPQKWLEXPLBMDLBPBKFAIJJKTMPZCOPYSGJFZWVPXBWXZ AJDGGTCBQGEMR...
output:
42995752
result:
ok single line: '42995752'
Test #5:
score: 0
Accepted
time: 32ms
memory: 72604kb
input:
250 70000 52 77 78 39 101 105 67 44 120 77 94 79 52 55 39 48 69 15 12 1 123 138 61 64 126 0 MUVQMZFNKVIJOXVUHNYKRENDWZQUWGWDPBIPAVPJZCYZEWCMAJINLQVRKTFZOXFOBZXCLCTBFKQDZXQQZRCVKHYHUHAEHOEHUVJXNOPLIFPHQTEABMROMUJKHXUKWAMSAJRCYYAKNBXRFHSJCGUFZZZZXIKFZIIYIRVDAQJLONKPPDQRQDIHLZJKQBJCUOFAULUILVYKHABQGZDV...
output:
762393745
result:
ok single line: '762393745'
Test #6:
score: 0
Accepted
time: 15ms
memory: 88652kb
input:
270 80000 165 90 72 119 141 144 110 63 169 23 17 101 164 121 125 35 1 142 114 167 142 111 49 5 41 84 HCDVASEIKNUXFHHRFAFDWEKPSCLBTQCWBZWGVCGXFEOEWBUTMEZKKNZBEDRHFZMURUTSDNDZPFNDAQLCDBSKCXWRACDHEWSYZIIGGARSEXFQQJIYFBDOBRGSXNWRWNULOHZWRZIJRQWIRRQUWVWJOQSEFAUGENOLJNOJOOYKNTJPXXHTCCRLOWWNDQENDTIEBTJZPWF...
output:
441440463
result:
ok single line: '441440463'
Test #7:
score: 0
Accepted
time: 24ms
memory: 102564kb
input:
280 90000 72 97 102 100 58 102 20 68 28 174 176 44 128 20 56 86 141 64 161 35 136 139 146 141 70 72 UYOKMOPRQXJGIKTKDQRYUKYCNSEXFTHJBBVSANHUHHQVNODOEOYITKYSLRJCTWOLFWCZSPDAZMOJYNJLVRIDWBMCRCWGSXRVWOTQLJHXMGHYCMNGILTZUWZFTSCHMNABCCECVZIIIMEPKYZPENQMQAKLUSXWMPSAIJXFGZBJUQSGGFWZFVOWHMDAHZTLKQUPFMEVAEAO...
output:
272071425
result:
ok single line: '272071425'
Test #8:
score: 0
Accepted
time: 47ms
memory: 111704kb
input:
290 95000 34 83 164 20 156 131 142 143 47 75 82 110 128 47 178 8 162 186 38 106 41 26 100 173 89 68 HDDJPDZQOBOINPUWEVSIPMUWIYAADZEKELHXMRTMGOKUVXZAHDWIPSPAPZBCSZTGCPEHAQKOZJHFXTNPVQMLYBRQWBEXATJPFHCCJDUPCYPVGPMIWICBHVAYLWHSORCJXSAAXEEWJXDLOLAAPBNKKJBXECLTXHIRCJUFPCSPXQPCBRIWABXLXLIGSBMZNNQFKWGQCFBI...
output:
498888329
result:
ok single line: '498888329'
Test #9:
score: 0
Accepted
time: 27ms
memory: 121548kb
input:
300 100000 134 97 138 61 185 82 54 8 195 28 25 2 89 73 31 59 60 161 136 27 191 148 28 36 125 8 QOFPONKNRXFBFKWCZWLKEQLSSAAGJRYTDEUABPSPMVYSUPZZTWTBQPYFMNMCQETODKIEEAFOOUTGDNXFGECTUVZJQYUXKUMMGJSJNBTRIQDONNBVGCMORLURVVRPSRNGXXAIDUNGFACNNDTVLVZZOJZGAWFFIGGGPJFTPSHQVAAUBIXYINZPTIZJOPWLKHPFUHJZPYLYKEZAU...
output:
381228834
result:
ok single line: '381228834'
Test #10:
score: 0
Accepted
time: 23ms
memory: 43132kb
input:
100 100000 36 79 106 150 95 148 86 102 50 53 6 111 56 72 176 181 164 33 35 199 145 179 64 180 9 186 JQMOUNUVXTFDIUXOJDIUOANBLVBOEVCEQWUNBBNQANUXUTBCCCVORSNJVNEDUCOORGWRXNADDPDGZRASGKHXGVXXEFGYVVVMBAME BOPCVNNYINSSCSOYNEBXXNLXACJMMIYOGKCCEKNXQYRYVLMQRINKBMNVWVQCPKGNHCUVDLVISUTENNVJTDAYXTWGGOSAFVQSINB...
output:
99529553
result:
ok single line: '99529553'
Test #11:
score: 0
Accepted
time: 17ms
memory: 62664kb
input:
150 100000 95 62 160 177 84 102 60 93 22 143 75 95 45 179 10 147 9 2 162 35 135 33 36 43 135 61 XPNWDUBBUXRZLFCKMKVXOLUBDTOPCQVSODFINYWRFBOLKOMWLAEUTFMZXRINISKFAZAUFVWZOLKHJLTJGPSZMHVHNVTESZVZTULOMNEVSZPQZLNOOYDBKJPMEJTRPJDNKGPVXCDAERBJLTLVQZXUKV XDGPYLODSSLQUZJXLEXLHSTRJNUEEVLHTNPPCJOTSNCMOPDWQYRFL...
output:
448361799
result:
ok single line: '448361799'
Test #12:
score: 0
Accepted
time: 30ms
memory: 82144kb
input:
200 100000 105 59 194 103 194 91 84 192 97 150 162 19 62 100 43 185 167 138 29 50 164 50 129 160 25 127 DDQRLPJTGDSYLHKVWPJGCNQYWTNBORFBFWHDWJFKIRUJQKEUJOMXOURAWUUVXXFXFYEWLBUPMAGCTZDVEIFDICNGUNBHPNTVLRRMOPZDSCYKLDXRUBGHDBZHBJXKKEUUPRKAGJFJFIPSRPZYXZXFPANSZCPWWUQNBWQXNYRZJBHTDDQBMWRVXVTQTBIQVFDUQNFJ...
output:
843022103
result:
ok single line: '843022103'
Test #13:
score: 0
Accepted
time: 40ms
memory: 101764kb
input:
250 100000 126 148 144 111 54 119 174 22 172 50 50 133 161 56 16 7 48 96 15 108 4 43 162 107 32 117 LWCIBVVZEWYEWEXKSFIHLQDSKYLYFBPQBOGHRSZNIUTFBJHXVUSPWSLROGXEGVQFAWWCKISQBCUUZYGIOLBWOSKFEETBAOSNOUQJHXARGDNYEOJCXOYCEXOTUZDKKRJTKDJFEOVMKYFTRDFIMGVCHLJZWCGOOPCFOGHWUEJMMFEJVMSIZGXDQTRMPDFYJAZFHPWFCNEV...
output:
346583537
result:
ok single line: '346583537'