oj.uz

Submission #252831

# Submission time Handle Problem Language Result Execution time Memory
252831 2020-07-26T10:30:38 Z NONAME Savez (COCI15_savez) C++14
0 / 120
 70 ms 16128 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());
        for (int j = 0; j < m; ++j)
            pf[j] = sum((j - 1 < 0 ? 0 : pf[j - 1]), mul((s[j] - 'A' + 1), power[j]));

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

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

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

        ans = max(ans, cur);

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

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

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 15992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 16000 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 16000 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 16120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 52 ms 16000 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 51 ms 16000 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 16000 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 16128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 60 ms 16120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 16000 KB Output isn't correct
2 Halted 0 ms 0 KB -