Submission #785931

#TimeUsernameProblemLanguageResultExecution timeMemory
785931MilosMilutinovicRima (COCI17_rima)C++14
56 / 140
345 ms106528 KiB
/** * 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 timeMemoryGrader output
Fetching results...