#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_map>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"
typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }
inline void io() {
#ifdef LOCAL_PROJECT
freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else
/* online submission */
#endif
ios_base::sync_with_stdio(false); cin.tie(NULL);
}
/**********************COCI 16-17 R2 P4 :(*****************************/
int N;
v<string> S;
v<v<ll>> normhsh, revhsh;
v<int> dp;
#define MOD 3949787434216469LL;
#define PRIME 211LL
ll p[2000010];
void computeHsh(int sidx) {
if (p[0] == 0) {
p[0] = 1;
FOR(i, 1, 2000010)
p[i] = (p[i - 1] * PRIME) % MOD;
}
FOR(i, 0, S[sidx].size()) {
normhsh[sidx][i] = (S[sidx][i] * PRIME) % MOD;
if (i) normhsh[sidx][i] = (normhsh[sidx][i] + normhsh[sidx][i - 1]) % MOD;
}
FOR(i, 0, S[sidx].size()) {
revhsh[sidx][i] = (S[sidx][S[sidx].size() - i - 1] * PRIME) % MOD;
if (i) revhsh[sidx][i] = (revhsh[sidx][i] + revhsh[sidx][i - 1]) % MOD;
}
}
int main() {
io();
cin >> N;
S.resize(N);
normhsh.resize(N);
revhsh.resize(N);
FOR(i, 0, N) {
cin >> S[i];
normhsh[i].resize(S[i].size());
revhsh[i].resize(S[i].size());
computeHsh(i);
}
int ans = 1;
dp.resize(N, 1);
RFORE(i, N - 1, 0) {
FOR(j, i + 1, N)
if (S[i].size() <= S[j].size() && normhsh[i].back() == normhsh[j][normhsh[i].size() - 1] && revhsh[i].back() == revhsh[j][revhsh[i].size() - 1])
maxx(dp[i], 1 + dp[j]);
maxx(ans, dp[i]);
}
cout << ans << "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
91 ms |
15992 KB |
Output is correct |
2 |
Incorrect |
24 ms |
15992 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
25 ms |
16212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
52 ms |
33744 KB |
Output is correct |
2 |
Correct |
53 ms |
34788 KB |
Output is correct |
3 |
Correct |
54 ms |
36164 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
27 ms |
36164 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
377 ms |
37608 KB |
Output is correct |
2 |
Correct |
479 ms |
38852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1088 ms |
40736 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1078 ms |
43888 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1075 ms |
47920 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1078 ms |
64092 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
154 ms |
66560 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |