oj.uz

Submission #250955

# Submission time Handle Problem Language Result Execution time Memory
250955 2020-07-19T16:37:13 Z kingfran1907 Savez (COCI15_savez) C++14
120 / 120
 109 ms 17912 KB 
#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

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.0 / 12.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 16000 KB Output is correct
2 Correct 17 ms 16000 KB Output is correct
3 Correct 22 ms 16128 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 17144 KB Output is correct
2 Correct 102 ms 17144 KB Output is correct
3 Correct 107 ms 17144 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 16128 KB Output is correct
2 Correct 50 ms 17272 KB Output is correct
3 Correct 69 ms 17272 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 17016 KB Output is correct
2 Correct 45 ms 17016 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 17016 KB Output is correct
2 Correct 47 ms 17036 KB Output is correct

Subtask #7
12.0 / 12.0

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

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 17016 KB Output is correct
2 Correct 58 ms 17016 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 17164 KB Output is correct
2 Correct 56 ms 17144 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 17400 KB Output is correct
2 Correct 66 ms 17320 KB Output is correct
3 Correct 109 ms 17912 KB Output is correct