Submission #745528

#	Time	Username	Problem	Language	Result	Execution time	Memory
745528		bgnbvnbv	Savez (COCI15_savez)	C++14	120 / 120	105 ms	17884 KiB

savez

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e6+10;
const ll inf=1e18;
const ll mod=1e9+7;
map<ll,ll> dp;
ll n;
string s;
ll hs[maxN];
ll pw[maxN];
ll get(int i,int j) {
    return (hs[j] - hs[i - 1] * pw[j - i + 1] + mod * mod) % mod;
}
const ll base=311;
void solve()
{
    cin >> n;
    ll ans=0;
    pw[0]=1;
    for(int i=1;i<maxN;i++) pw[i]=pw[i-1]*base%mod;
    for(int i=1;i<=n;i++)
    {
        cin >> s;
        s=' '+s;
        ll m=s.size()-1;
        ll val=1;
        for(int j=1;j<=m;j++)
        {
            hs[j]=(hs[j-1]*base+s[j])%mod;
        }
        for(int j=1;j<=m;j++)
        {
            if(get(1,j)==get(m-j+1,m))
            {
                val=max(val,dp[get(1,j)]+1);
            }
        }
        dp[hs[m]]=max(dp[hs[m]],val);
        ans=max(ans,val);
    }
    cout << ans;
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

• 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