oj.uz

Submission #745528

# Submission time Handle Problem Language Result Execution time Memory
745528 2023-05-20T09:47:09 Z bgnbvnbv Savez (COCI15_savez) C++14
120 / 120
 105 ms 17884 KB 
#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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 15956 KB Output is correct
2 Correct 15 ms 15952 KB Output is correct
3 Correct 15 ms 15916 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 15924 KB Output is correct
2 Correct 15 ms 15956 KB Output is correct
3 Correct 16 ms 16032 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 17092 KB Output is correct
2 Correct 95 ms 17104 KB Output is correct
3 Correct 95 ms 17004 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16084 KB Output is correct
2 Correct 44 ms 17032 KB Output is correct
3 Correct 66 ms 17300 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 17000 KB Output is correct
2 Correct 34 ms 16980 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 16880 KB Output is correct
2 Correct 34 ms 16972 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 17020 KB Output is correct
2 Correct 35 ms 16932 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 17100 KB Output is correct
2 Correct 36 ms 17144 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 17124 KB Output is correct
2 Correct 47 ms 17144 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 17360 KB Output is correct
2 Correct 62 ms 17340 KB Output is correct
3 Correct 105 ms 17884 KB Output is correct