oj.uz

Submission #937306

# Submission time Handle Problem Language Result Execution time Memory
937306 2024-03-03T19:36:44 Z BidoTeima Savez (COCI15_savez) C++17
120 / 120
 73 ms 22904 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;    
const int N = 2e6 + 3;
const ll mod = 1e18 + 3, base = 31;
ll mul(ll a, ll b){
    return (__int128(a) * b) % mod;
}
ll add(ll a, ll b){
    return a + b >= mod ? a + b - mod : a + b;
}
int dp[N];
map<ll,int>idx{};
ll pw[N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);  
    pw[0] = 1;
    for(int i = 1; i < N; i++){
        pw[i] = mul(pw[i - 1], base);
    }
    int n;
    cin>>n;
    for(int i = 0; i < n; i++){
        dp[i] = 1;
        string s;
        cin>>s;
        string rv = s;
        reverse(rv.begin(), rv.end());
        ll hashp = 0, hashs = 0;
        for(int j = 0; j < (int)s.size(); j++){
            hashp = add(mul(hashp, base), s[j] - 'A' + 1);
            hashs = add(mul(pw[j], rv[j] - 'A' + 1), hashs);
            //cout<<hashp<<' '<<hashs<<'/';
            if(hashp == hashs){
                auto it = idx.find(hashp);
                if(it != idx.end()){
                    dp[i] = max(dp[i], dp[it->second] + 1);
                }
            }
        }
        idx[hashp] = i;
        //cout<<'\n';
    }
    cout<<*max_element(dp, dp + n + 1);
    return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 17000 KB Output is correct
2 Correct 13 ms 16988 KB Output is correct
3 Correct 13 ms 17240 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 17024 KB Output is correct
2 Correct 13 ms 16988 KB Output is correct
3 Correct 14 ms 17140 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 18004 KB Output is correct
2 Correct 30 ms 18012 KB Output is correct
3 Correct 52 ms 18068 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16988 KB Output is correct
2 Correct 32 ms 18260 KB Output is correct
3 Correct 38 ms 18012 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 18000 KB Output is correct
2 Correct 27 ms 17800 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 18012 KB Output is correct
2 Correct 27 ms 18012 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 18004 KB Output is correct
2 Correct 32 ms 17800 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 18004 KB Output is correct
2 Correct 30 ms 18000 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 20052 KB Output is correct
2 Correct 37 ms 20104 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 20544 KB Output is correct
2 Correct 47 ms 20364 KB Output is correct
3 Correct 73 ms 22904 KB Output is correct