Submission #250955

#	Time	Username	Problem	Language	Result	Execution time	Memory
250955		kingfran1907	Savez (COCI15_savez)	C++14	120 / 120	109 ms	17912 KiB

savez

#include <bits/stdc++.h>

using namespace std;
typedef long long llint;

const int maxn = 2e6+10;
const llint base = 31337;
const llint mod = 1e9+9;

int n;
map< llint, int > dp;
llint pot[maxn];
vector< llint > v;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;

    pot[0] = 1;
    for (int i = 1; i < maxn; i++)
        pot[i] = pot[i - 1] * base, pot[i] %= mod;

    int sol = 0;
    while (n--) {
        string a;
        cin >> a;

        v.clear();
        v.push_back(0);
        for (int i = 0; i < a.size(); i++) {
            llint tren = v.back() * base;
            tren %= mod;
            tren += a[i], tren %= mod;
            v.push_back(tren);
        }

        int tren = 0;
        for (int i = 1; i < v.size(); i++) {
            //printf("debug: %d/%d\n", i, v.size());
            //printf("has: %lld == %lld\n", v[i], (v.back() - ((v[v.size() - 1 - i] * pot[i]) % mod) + mod) % mod);
            if (v[i] == (v.back() - ((v[v.size() - 1 - i] * pot[i]) % mod) + mod) % mod)
                tren = max(tren, dp[v[i]]);
        }
        tren++;

        sol = max(sol, tren);
        int &ac = dp[v.back()];
        ac = max(ac, tren);
    }
    printf("%d", sol);
    return 0;
}

Compilation message (stderr)

savez.cpp: In function 'int main()':
savez.cpp:31:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < a.size(); i++) {
                         ~~^~~~~~~~~~
savez.cpp:39:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 1; i < v.size(); i++) {
                         ~~^~~~~~~~~~

• 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