Submission #937306

#	Time	Username	Problem	Language	Result	Execution time	Memory
937306		BidoTeima	Savez (COCI15_savez)	C++17	120 / 120	73 ms	22904 KiB

savez

#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 / 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