Submission #81894

#	Time	Username	Problem	Language	Result	Execution time	Memory
81894		ngot23	Rima (COCI17_rima)	C++11	14 / 140	1096 ms	197444 KiB

rima

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i=(a) ; i<=(b) ; ++i)
#define Task ""
using namespace std;
const int N=500005;
const int mod=1000000007;
const long long MM=1ll*mod*mod;
const int base=191;
long long h[3000001], Hash[3000001];
set <pair<int, int > > s[3000001];
string str[N];
int dp[N], n, mx, ans;

void setup() {
    cin >> n;
    rep(i, 1, n) {
        cin >> str[i];
        mx=max(mx, (int)str[i].size());
    }
}

long long get(int u, int v) {
    return (Hash[v]-Hash[u-1]*h[v-u+1]+MM)%mod;
}

void xuli(int id) {
    string ss=str[id];
    int leng=ss.size();
    ss=' '+ss;
    rep(i, 1, leng) {
        Hash[i]=(Hash[i-1]*base+ss[i])%mod;
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen(Task".inp", "r", stdin);
    //freopen(Task".out", "w", stdout);
    setup();
    h[0]=1;
    rep(i, 1, mx) h[i]=(h[i-1]*base)%mod;
    rep(i, 1, n) {
        dp[i]=1;
        xuli(i);
        int leng=str[i].size();
        long long hash2=get(2, leng);
        if(s[leng].size()) {
            auto it=s[leng].upper_bound(make_pair(Hash[leng], 1000000000));
            if(it!=s[leng].begin()) {
                --it;
                if(it->first==Hash[leng])
                    dp[i]=max(dp[i], dp[it->second]+1);
            }

            it=s[leng].upper_bound(make_pair(hash2, 1000000000));
            if(it!=s[leng].begin()) {
                --it;
                if(it->first==hash2) dp[i]=max(dp[i], dp[it->second]+1);
            }
        }

        if(s[leng+1].size()) {
            auto it=s[leng+1].upper_bound(make_pair(Hash[leng], 1000000000));
            if(it!=s[leng+1].begin()) {
                --it;
                if(it->first==Hash[leng]) dp[i]=max(dp[i], dp[it->second]+1);
            }
        }

        s[leng].insert(make_pair(Hash[n], i));
        s[leng].insert(make_pair(hash2, i));
    }
    rep(i, 1, n) ans=max(ans, dp[i]);
    cout << ans;
    return 0;
}

• Subtask 1: 14 / 140