QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#645012 | #6366. Message | PPPxvchongyv | WA | 3ms | 10392kb | C++14 | 2.3kb | 2024-10-16 16:29:05 | 2024-10-16 16:29:05 |
Judging History
answer
#include <bits/stdc++.h>
std::vector<int> KMPed(const std::string &a, std::string g) {
g = '`' + g;
std::vector<int> b(g.length(), 0);
b[0] = -1;
for(int i = 1; i < g.length(); i++) {
int p = b[i - 1];
while(p != -1)
if(g[p + 1] != g[i])
p = b[p];
else
break;
b[i] = p + 1;
}
std::vector<int> res;
int k = 0;
for(int i = 0; i < a.length(); i++) {
while(k >= 0 && a[i] != g[k + 1])
k = b[k];
k++;
if(k == g.length() - 1)
res.push_back(i), k = b[k];
}
return res;
}
constexpr long long Inf = 3141592653589793238LL;
char a[262144], b[262144];
int n, m, t[262144];
long long st[262144];
std::array<int, 32> bl, br;
std::array<long long, 262144> f, g;
std::vector<int> u;
int main() {
scanf("%s%s", a + 1, b + 1), n = strlen(a + 1), m = strlen(b + 1);
for(int i = 1; i <= n; i++)
a[i] -= '`';
for(int i = 1; i <= m; i++)
b[i] -= '`';
for(int i = 1; i <= n; i++)
scanf("%d", &t[i]);
bl.fill(m), br.fill(1);
for(int i = 1; i <= m; i++)
bl[b[i]] = std::min(bl[b[i]], i),
br[b[i]] = std::max(br[b[i]], i);
for(int i = 0; i <= 26; i++)
u.push_back(bl[i]), u.push_back(br[i] + 1);
std::sort(u.begin(), u.end()),
u.erase(std::unique(u.begin(), u.end()), u.end());
f[0] = -Inf;
for(int j = 1; j <= n; j++)
f[j] = std::min(f[j], f[j - 1] + t[j]);
for(int i = 1; i < u.size(); i++) {
std::string filt;
std::bitset<32> has;
std::vector<int> filtered;
for(int j = 1; j <= 26; j++)
has[j] = bl[j] <= u[i - 1] && u[i] - 1 <= br[j];
for(int j = 1; j <= n; j++)
if(has[a[j]])
filt.push_back(a[j]), filtered.push_back(j);
for(int j = 1; j <= n; j++)
st[j] = st[j - 1] + (has[a[j]] ? 0 : t[j]);
for(int j = 1; j <= n; j++)
if(!has[a[j]] || bl[j] == u[i - 1])
f[j] = std::min(f[j], f[j - 1] + t[j]);
std::vector<int> yes = KMPed(filt, std::string(b + u[i - 1], b + u[i]));
g.fill(0);
for(int j : yes) {
int l = filtered[j + u[i - 1] - u[i] + 1] - 1, r = filtered[j];
g[r] = std::min(g[r], f[l] + st[r] - st[l]);
}
std::swap(f, g);
for(int j = 1; j <= n; j++)
if(!has[a[j]] || br[j] + 1 == u[i])
f[j] = std::min(f[j], f[j - 1] + t[j]);
}
for(int j = 1; j <= n; j++)
f[j] = std::min(f[j], f[j - 1] + t[j]);
printf("%lld\n", f[n] < 0 ? f[n] + Inf : -1);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 9864kb
input:
ababccb abc 7 2 2 4 3 2 1
output:
7
result:
ok single line: '7'
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 10392kb
input:
babab baab 2 1 3 2 4
output:
-1
result:
wrong answer 1st lines differ - expected: 'You better start from scratch man...', found: '-1'