Submission #1006383

#TimeUsernameProblemLanguageResultExecution timeMemory
1006383MilosMilutinovicRima (COCI17_rima)C++14
56 / 140
483 ms63972 KiB
#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]; } for (int i = 0; i < n; i++) { reverse(s[i].begin(), s[i].end()); } sort(s.begin(), s.end(), [&](string s, string t) { int cs = (int) s.size(); int ct = (int) t.size(); if (cs != ct) { return cs < ct; } else { return s < t; } }); map<string, int> f; auto Modify = [&](string s, int val) { f[s] = max(f[s], val); }; auto Query = [&](string s) { s.pop_back(); return f[s]; }; auto Good = [&](string s, string t) { s.pop_back(); t.pop_back(); return s == t; }; for (int i = 0; i < n; i++) { int ptr = i; while (ptr + 1 < n && (int) s[ptr + 1].size() == (int) s[i].size()) { ptr += 1; } for (int l = i; l <= ptr; l++) { int r = l; while (r + 1 <= ptr && Good(s[l], s[r + 1])) { r += 1; } int ft = Query(s[l]) + (r - l + 1); for (int p = l; p <= r; p++) { Modify(s[p], ft); } l = r; } i = ptr; } int res = 0; for (auto& p : f) { res = max(res, p.second); } cout << res << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...