oj.uz

Submission #252835

# Submission time Handle Problem Language Result Execution time Memory
252835 2020-07-26T10:42:32 Z NONAME Savez (COCI15_savez) C++14
120 / 120
 111 ms 18104 KB 
#include <bits/stdc++.h>
#define dbg(x) cerr << #x << " = " << x << "\n"
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie()
using namespace std;
using ll = long long;

const int N = int(2e6) + 10;
const ll base = int(1e9) + 7;

ll n, power[N], pf[N], ans;
map <ll, ll> dp;

ll sum(ll x, ll y) { return (x + y) % base; }
ll mul(ll x, ll y) { return (x * y) % base; }
ll dec(ll x, ll y) { x -= y; while (x < 0) x += base; return x; }

int main() {
    fast_io;

    cin >> n;

    power[0] = 1;
    for (int i = 1; i <= int(2e6); ++i)
        power[i] = mul(power[i - 1], 29ll);

    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        int m = int(s.size());
        pf[0] = 0;
        for (int j = 0; j < m; ++j)
            pf[j + 1] = sum(mul(pf[j], 29ll), (s[j] - 'A' + 1));

        ll cur = 1;
        for (int j = 1; j <= m; ++j) {
            ll pref = dec(pf[j], mul(pf[0], power[j]));
            ll suff = dec(pf[m], mul(pf[m - j], power[j]));

            //cerr << s << " " << pref << " " << suff << " " << pf[j] << "\n";
            if (pref != suff || dp.find(pf[j]) == dp.end())
                continue;

            cur = max(cur, dp[pf[j]] + 1);
        }

        ans = max(ans, cur);

        dp[pf[m]] = max(dp[pf[m]], cur);
    }

    cout << ans << "\n";
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 16000 KB Output is correct
2 Correct 19 ms 15992 KB Output is correct
3 Correct 19 ms 15992 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 16000 KB Output is correct
2 Correct 19 ms 15992 KB Output is correct
3 Correct 20 ms 16000 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 16028 KB Output is correct
2 Correct 48 ms 16000 KB Output is correct
3 Correct 76 ms 17016 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 16000 KB Output is correct
2 Correct 61 ms 16072 KB Output is correct
3 Correct 61 ms 16120 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 16120 KB Output is correct
2 Correct 45 ms 16940 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 16000 KB Output is correct
2 Correct 49 ms 17016 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 16000 KB Output is correct
2 Correct 48 ms 17016 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 15992 KB Output is correct
2 Correct 50 ms 17016 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 16000 KB Output is correct
2 Correct 60 ms 17180 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 16000 KB Output is correct
2 Correct 68 ms 17400 KB Output is correct
3 Correct 111 ms 18104 KB Output is correct