Submission #252835

#	Time	Username	Problem	Language	Result	Execution time	Memory
252835		NONAME	Savez (COCI15_savez)	C++14	120 / 120	111 ms	18104 KiB

savez

#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 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 12 / 12
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12