QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#833322 | #2354. Ook | I_Love_Sonechka# | WA | 0ms | 3780kb | C++20 | 3.7kb | 2024-12-26 17:13:43 | 2024-12-26 17:13:48 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#ifdef ONPC
#define deb(...) cerr << '[' << __LINE__ << "] (" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define deb(...)
#endif
// c++ short types
#define vt vector
//typedef long long ll;
typedef long double ld;
void whattime() { cout << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl; }
// const int mod = 1e9 + 7;
const int mod = 998244353;
const int inf = 1e9;
const int64_t infll = 1e13;
bool debug = false;
const ld eps = 1e-9;
const ld pi = acos(-1);
mt19937_64 rng((int) chrono::steady_clock::now().time_since_epoch().count());
const int K = 3;
int getId(char c) {
if(c == 'o') {
return 0;
} else if(c == 'k') {
return 1;
} else {
// assert(c == '?');
return 2;
}
}
struct Vertex {
int next[K];
bool output = false;
int p = -1, link = -1;
char pch;
int go[K];
Vertex(int p = -1, char ch = '$') : p(p), pch(ch) {
fill(next, next + K, -1);
fill(go, go + K, -1);
}
};
vt<Vertex> t(1);
void add_string(const string &s) {
int v = 0;
for(char ch: s) {
int c = getId(ch);
if(t[v].next[c] == -1) {
t[v].next[c] = t.size();
t.emplace_back(v, ch);
}
v = t[v].next[c];
}
t[v].output = true;
}
int go(int v, char ch);
int get_link(int v) {
if(t[v].link == -1) {
if(v == 0 || t[v].p == 0) {
return t[v].link = 0;
} else {
t[v].link = go(get_link(t[v].p), t[v].pch);
}
}
return t[v].link;
}
int go(int v, char ch) {
int c = getId(ch);
if(t[v].go[c] == -1) {
if(c == 2) {
for(int i = 0; i < K; ++i) {
t[v].go[c] = max(t[v].go[c], t[v].next[i]);
}
} else {
t[v].go[c] = max(t[v].next[c], t[v].next[2]);
if(t[v].go[c] == -1) {
t[v].go[c] = v == 0 ? 0 : go(get_link(v), ch);
}
}
}
return t[v].go[c];
}
void solve() {
int o, k;
cin >> o >> k;
string s, p;
cin >> s >> p;
if(s.size() < p.size()) {
cout << "0\n";
return ;
}
add_string(p);
int cost = 0;
vt<int> dp(s.size(), 0), vertices(32, 0);
for(int i = 0; i < int(s.size()); ++i) {
if(i) {
dp[i] = dp[i-1];
}
if(i >= p.size()) {
if(s[i - p.size()] == 'o') {
cost -= o;
} else {
cost -= k;
}
}
if(s[i] == 'o') {
cost += o;
} else {
cost += k;
}
for(int j = vertices.size() - 1; j >= 0; --j) {
vertices[j] = go(vertices[j], s[i]);
if(j) {
vertices[j] = max(vertices[j], go(vertices[j-1], '?'));
}
}
int z = 33;
for(int j = 0; j < int(vertices.size()); ++j) {
if(t[vertices[j]].output) {
z = j;
break;
}
}
// deb(i, cost, z);
if(i + 1 >= p.size()) {
int value = cost >> z;
if(i - (int)p.size() >= 0) {
value += dp[i-p.size()];
}
// deb(value);
dp[i] = max(dp[i], value);
}
}
cout << dp.back() << '\n';
}
int main()
{
// ios::sync_with_stdio(false); cin.tie(nullptr);
#ifdef ONPC
freopen("C:\\Users\\raf4i\\CLionProjects\\cp\\inp.txt", "r", stdin);
#endif
int tt = 1;
if(debug) {
tt = 1e6;
} else {
// cin >> tt;
}
for(int t = 0; t < tt; ++t) {
solve();
}
#ifdef ONPC
whattime();
#endif
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3608kb
input:
2 1 ookookook koo
output:
10
result:
ok single line: '10'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
1 3 koooooook ?
output:
13
result:
ok single line: '13'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
1000 0 kookoo ook
output:
2000
result:
ok single line: '2000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
21 1 ooo kkk
output:
7
result:
ok single line: '7'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
1 0 ookko k??ko
output:
1
result:
ok single line: '1'
Test #6:
score: -100
Wrong Answer
time: 0ms
memory: 3556kb
input:
5 8 koookokkok oo
output:
36
result:
wrong answer 1st lines differ - expected: '32', found: '36'