/**
* author: wxhtzdy
* created: 17.07.2023 21:12:57
**/
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<string> s(n);
for (int i = 0; i < n; i++) {
cin >> s[i];
reverse(s[i].begin(), s[i].end());
}
sort(s.begin(), s.end(), [&](string s, string t) {
if (s.size() != t.size()) {
return s.size() < t.size();
} else {
return s < t;
}
});
const int A = 26;
vector<vector<int>> trie(1, vector<int>(A, -1));
vector<int> f0(n), f1(n);
for (int i = 0; i < n; i++) {
int nd = 0;
for (int j = 0; j < (int) s[i].size(); j++) {
int x = (int) (s[i][j] - 'a');
if (trie[nd][x] == -1) {
trie[nd][x] = (int) trie.size();
trie.push_back(vector<int>(A, -1));
}
nd = trie[nd][x];
if (j == (int) s[i].size() - 2) {
f0[i] = nd;
}
if (j == (int) s[i].size() - 1) {
f1[i] = nd;
}
}
}
int sz = (int) trie.size();
vector<int> dp(sz);
for (int i = 0; i < n; i++) {
int ptr = i;
while (ptr + 1 < n && f0[ptr + 1] == f0[i]) {
ptr += 1;
}
int cnt = ptr - i + 1;
int ndp = dp[f0[i]] + cnt;
for (int j = i; j <= ptr; j++) {
dp[f1[j]] = max(dp[f1[j]], ndp);
}
i = ptr;
}
cout << *max_element(dp.begin(), dp.end()) << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
102 ms |
16972 KB |
Output isn't correct |
| 2 |
Incorrect |
99 ms |
16528 KB |
Output isn't correct |
| 3 |
Incorrect |
120 ms |
20436 KB |
Output isn't correct |
| 4 |
Incorrect |
124 ms |
20940 KB |
Output isn't correct |
| 5 |
Incorrect |
236 ms |
21160 KB |
Output isn't correct |
| 6 |
Incorrect |
253 ms |
21104 KB |
Output isn't correct |
| 7 |
Incorrect |
283 ms |
21988 KB |
Output isn't correct |
| 8 |
Incorrect |
235 ms |
19724 KB |
Output isn't correct |
| 9 |
Incorrect |
282 ms |
23392 KB |
Output isn't correct |
| 10 |
Incorrect |
283 ms |
23384 KB |
Output isn't correct |
