제출 #631004

#제출 시각아이디문제언어결과실행 시간메모리
631004inksamuraiRima (COCI17_rima)C++17
14 / 140
1096 ms70840 KiB
#include <bits/stdc++.h> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) #define rng(i,c,n) for(int i=c;i<n;i++) #define per(i,n) for(int i=n-1;i>=0;i--) #define fi first #define se second #define pb push_back #define sz(a) (int)a.size() #define vec(...) vector<__VA_ARGS__> #define _3phCa4T ios::sync_with_stdio(0),cin.tie(0) typedef long long ll; using pii=pair<int,int>; using vi=vector<int>; void print(){cout<<'\n';} template<class h,class...t> void print(const h&v,const t&...u){cout<<v<<' ',print(u...);} // e //snuke's mod int template <ll mod> struct modint{ ll x; // typedef long long ll; modint(ll x=0):x((x%mod+mod)%mod){} modint operator-()const{return modint(-x);} modint& operator+=(const modint a){if((x+=a.x)>=mod) x-=mod; return *this;} modint& operator-=(const modint a){if((x+=mod-a.x)>=mod) x-=mod; return *this;} modint& operator*=(const modint a){(x*=a.x)%=mod; return *this;} modint operator+(const modint a)const{modint res(*this); return res+=a;} modint operator-(const modint a)const{modint res(*this); return res-=a;} modint operator*(const modint a)const{modint res(*this); return res*=a;} modint pow(ll n)const{ modint res=1,x(*this); while(n){ if(n&1)res*=x; x*=x; n>>=1; } return res; } modint inv()const{return pow(mod-2);} }; using mint=modint<998244353>; // include mint here using hshmint=modint<1000000007>; using hshmint1=modint<998244353>; using magicpair=pair<hshmint,hshmint1>; struct rollhsh{ hshmint _p=9973; // base hshmint1 _p1=257; // base1 vec(hshmint) pw,invpw; vec(hshmint1) pw1,invpw1; vec(magicpair) hsh; rollhsh(string s=""){ init(s); } void init(string s){ // put this out in global if multiple testcases hsh.clear(); pw.clear(); invpw.clear(); pw1.clear(); invpw1.clear(); hsh.resize(sz(s)+1); pw.resize(sz(s)+1); invpw.resize(sz(s)+1); pw1.resize(sz(s)+1); invpw1.resize(sz(s)+1); hsh[0]={1,1}; pw[0]=1; pw1[0]=1; invpw[0]=1; invpw1[0]=1; hshmint _invbase=_p.x; hshmint1 _invbase1=_p1.x; _invbase=_invbase.inv(); _invbase1=_invbase1.inv(); rep(i,sz(s)){ pw[i+1]=pw[i]*_p; pw1[i+1]=pw1[i]*_p1; invpw[i+1]=invpw[i]*_invbase; invpw1[i+1]=invpw1[i]*_invbase1; hshmint x=(int)(s[i]-'a'+1); hshmint1 x1=(int)(s[i]-'a'+1); hsh[i+1]={hsh[i].fi+pw[i]*x,hsh[i].se+pw1[i]*x1}; } } pair<ll,ll> get(int l,int r){ // from - to , inclusive hshmint _f=invpw[l]*(hsh[r+1].fi-hsh[l].fi); hshmint1 _s=invpw1[l]*(hsh[r+1].se-hsh[l].se); return {_f.x,_s.x}; } }; signed main(){ _3phCa4T; int n; cin>>n; vec(string) a; rep(i,n){ string s; cin>>s; a.pb(s); } using pll=pair<ll,ll>; std::map<pll,int> dp,pd,sdp; rollhsh hsh; rep(i,n){ hsh.init(a[i]); pll p=hsh.get(1,sz(a[i])-1); pll q=hsh.get(0,sz(a[i])-1); int val=max({dp[p],pd[q],sdp[p]})+1; // print(i,val); dp[q]=max(dp[q],val); pd[p]=max(dp[p],val); sdp[p]=max(sdp[p],val); } int res=0; for(auto p:dp)res=max(res,p.se); print(res); }
#Verdict Execution timeMemoryGrader output
Fetching results...