Submission #785952

#TimeUsernameProblemLanguageResultExecution timeMemory
785952MilosMilutinovicRima (COCI17_rima)C++14
42 / 140
1094 ms18020 KiB
/** * author: wxhtzdy * created: 17.07.2023 22:01:28 **/ #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; } }); auto Check = [&](string s, string t) { int ptr = 0; int si = (int) s.size(); int sj = (int) t.size(); while (ptr < min(si, sj) && s[ptr] == t[ptr]) { ptr += 1; } return (ptr >= max(si, sj) - 1); }; auto Same = [&](string s, string t) { s.pop_back(); t.pop_back(); return s == t; }; vector<int> dp(n); for (int i = 0; i < n; i++) { int ptr = i; while (ptr + 1 < n && Same(s[i], s[ptr + 1])) { ptr += 1; } int cnt = ptr - i + 1; int mx = 0; for (int j = 0; j < i; j++) { if (Check(s[i], s[j])) { mx = max(mx, dp[j]); } } for (int j = i; j <= ptr; j++) { dp[j] = mx + cnt; } i = ptr; } cout << *max_element(dp.begin(), dp.end()) << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...