oj.uz

Submission #94051

# Submission time Handle Problem Language Result Execution time Memory
94051 2019-01-15T06:34:02 Z tmwilliamlin168 Rima (COCI17_rima) C++14
140 / 140
 228 ms 68472 KB 
#include <bits/stdc++.h>
using namespace std;

const int mxS=3e6+1;
int n, m=1, c[mxS][26], dp[mxS], ans;
string s;
bool a[mxS];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	while(n--) {
		cin >> s;
		int u=0;
		for(int i=s.size()-1; i>=0; u=c[u][s[i]-'a'], --i)
			if(!c[u][s[i]-'a'])
				c[u][s[i]-'a']=m++;
		a[u]=1;
	}
	while(m--) {
		int nc=0;
		for(int i=0; i<26; ++i)
			nc+=a[c[m][i]];
		dp[m]=a[m];
		for(int i=0; i<26; ++i) {
			if(!a[c[m][i]])
				continue;
			ans=max(dp[c[m][i]]+dp[m]+nc-2, ans);
			dp[m]=max(dp[c[m][i]]+a[m], dp[m]);
		}
		dp[m]=max(a[m]+nc, dp[m]+nc-1);
		ans=max(dp[m], ans);
	}
	cout << ans;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 228 ms 68472 KB Output is correct
5 Correct 26 ms 3448 KB Output is correct
6 Correct 51 ms 33292 KB Output is correct
7 Correct 51 ms 33188 KB Output is correct
8 Correct 52 ms 33116 KB Output is correct
9 Correct 69 ms 36968 KB Output is correct
10 Correct 50 ms 33020 KB Output is correct