# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
305407 | 2020-09-23T02:57:43 Z | FlashGamezzz | Rima (COCI17_rima) | C++17 | 306 ms | 65724 KB |
#include <iostream> #include <cstdlib> #include <cstdio> #include <fstream> #include <algorithm> #include <string> #include <utility> #include <vector> #include <queue> using namespace std; bool endw[3000000] = {}; int lets[3000000][26] = {}, dp[3000000] = {}, sz = 1, ans = 0; string s; void add(int c, int i){ if (i == s.length()){ endw[c] = true; return; } int l = int(s[s.length()-i-1])-97; if (lets[c][l] == 0){ lets[c][l] = sz; sz++; } add(lets[c][l], i+1); } void solve(int c){ vector<int> vals; for (int i = 0; i < 26; i++){ if (lets[c][i] > 0){ solve(lets[c][i]); if (endw[lets[c][i]]){ dp[c]++; vals.push_back(dp[lets[c][i]]); } } } sort(vals.begin(), vals.end()); if (vals.size() >= 1){ dp[c] += vals[vals.size()-1]; } int t = dp[c]; if (endw[c]){ t++; } if (vals.size() >= 2){ t += vals[vals.size()-2]; } ans = max(ans, t); } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; for (int i = 0; i < n; i++){ cin >> s; add(0, 0); } solve(0); cout << ans << endl; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 0 ms | 384 KB | Output is correct |
3 | Correct | 0 ms | 384 KB | Output is correct |
4 | Correct | 306 ms | 65724 KB | Output is correct |
5 | Correct | 17 ms | 768 KB | Output is correct |
6 | Correct | 59 ms | 55052 KB | Output is correct |
7 | Correct | 56 ms | 54936 KB | Output is correct |
8 | Correct | 57 ms | 55000 KB | Output is correct |
9 | Correct | 80 ms | 56404 KB | Output is correct |
10 | Correct | 60 ms | 55036 KB | Output is correct |