# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
632405 | Neos | Savez (COCI15_savez) | C++14 | 116 ms | 6092 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using ii = pair<ll, ll>;
#define fastIO ios::sync_with_stdio(0); cin.tie(0);
#define fi first
#define se second
#define pb push_back
#define numBit(x) (__builtin_popcountll(1ll * (x)))
#define getBit(x, i) ((x) >> (i) & 1)
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define MASK(x) 1ll << (x)
template<class X, class Y>
bool minimize(X &x, const Y &y) {
X eps = 1e-9;
if (x > y + eps) {
x = y;
return true;
} else return false;
}
template<class X, class Y>
bool maximize(X &x, const Y &y) {
X eps = 1e-9;
if (x + eps < y) {
x = y;
return true;
} else return false;
}
const int N = 2e6 + 7;
const int base = 311, MOD = 1e9 + 7;
int n;
vector<int> dp;
string s;
map<int, int> mp;
struct Hash {
string s;
int n;
vector<int> hsh, pw;
void init(string x) {
s = x; n = sz(s); s = ' ' + s;
hsh.resize(n + 1, 0); pw.resize(n + 1, 1);
for(int i = 1; i <= n; i++) {
pw[i] = 1ll * pw[i - 1] * base % MOD;
hsh[i] = (1ll * hsh[i - 1] * base % MOD + s[i]) % MOD;
}
}
int get(int l, int r) {
return (hsh[r] - 1ll * hsh[l - 1] * pw[r - l + 1] % MOD + MOD) % MOD;
}
} H;
int ans = 0, tmp = 1;
signed main() {
fastIO;
if (fopen("test.inp", "r")) {
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
}
if (fopen("savez.inp", "r")) {
freopen("savez.inp", "r", stdin);
freopen("savez.out", "w", stdout);
}
cin >> n;
dp.resize(n + 1);
for (int i = 1; i <= n; i++) {
cin >> s; H.init(s); tmp = 1;
for (int j = 1; j <= sz(s); j++) {
if (H.get(1, j) == H.get(sz(s) - j + 1, sz(s)) && mp.find(H.get(1, j)) != mp.end()) {
tmp = max(tmp, dp[mp[H.get(1, j)]] + 1);
}
}
maximize(ans, tmp); mp[H.get(1, sz(s))] = i; dp[mp[H.get(1, sz(s))]] = tmp;
}
cout << ans;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |