最后之作

C++14(g++5.4) 解法, 执行用时: 1628ms, 内存消耗: 207916K, 提交时间: 2019-06-03 20:24:46

#include<bits/stdc++.h>
#define il inline
#define vd void
#define ll long long
il int gi(){
	int x=0,f=0;char ch=getchar();
	while(!isdigit(ch))f^=ch=='-',ch=getchar();
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	return f?-x:x;
}
int n,m,N;
int a[1000010],b[1000010];
char s[1000010];
namespace SA{
	int SA[1000010],rk[1000010],t[1000010],ht[1000010],x[1000010],y[1000010];
	int st[20][1000010],lg[1000010];
	il int gety(int p){return p<=N?y[p]:-1;}
	il int LCP(int x,int y){
		if(x>y)std::swap(x,y);
		int g=lg[y-x];
		return std::min(st[g][x],st[g][y-(1<<g)]);
	}
	il vd getSA(){
		int set=128;
		for(int i=1;i<=N;++i)++t[x[i]=s[i]];
		for(int i=1;i<=set;++i)t[i]+=t[i-1];
		for(int i=N;i;--i)SA[t[x[i]]--]=i;
		for(int k=1;k<=N;k<<=1){
			int p=0;
			for(int i=N-k+1;i<=N;++i)y[++p]=i;
			for(int i=1;i<=N;++i)if(SA[i]>k)y[++p]=SA[i]-k;
			for(int i=1;i<=set;++i)t[i]=0;
			for(int i=1;i<=N;++i)++t[x[y[i]]];
			for(int i=1;i<=set;++i)t[i]+=t[i-1];
			for(int i=N;i;--i)SA[t[x[y[i]]]--]=y[i];
			std::swap(x,y);x[SA[1]]=p=1;
			for(int i=2;i<=N;++i){
				if(y[SA[i-1]]!=y[SA[i]]||y[SA[i-1]+k]!=y[SA[i]+k])++p;
				x[SA[i]]=p;
			}
			set=p;if(set>=N)break;
		}
		for(int i=1;i<=N;++i)rk[SA[i]]=i;
		s[N+1]='%';
		for(int i=1,j,k=0;i<=N;++i){
			if(rk[i]==N)continue;
			if(k)--k;j=SA[rk[i]+1];
			while(s[i+k]==s[j+k])++k;
			ht[rk[i]]=k;
		}
		for(int i=2;i<=N;++i)lg[i]=lg[i>>1]+1;
		for(int i=1;i<=N;++i)st[0][i]=ht[i];
		for(int i=1;i<=lg[N];++i)
			for(int j=1;j+(1<<i)-1<=N;++j)
				st[i][j]=std::min(st[i-1][j],st[i-1][j+(1<<i-1)]);
	}
}
int t[1000010];
ll dp[1000010];
struct line{ll k,b;template<class T>il T get(T x)const{return k*x+b;}};
il bool operator<(const line&a,const line&b){return a.k<b.k;}
il double crossx(const line&a,const line&b){return 1.0*(a.b-b.b)/(b.k-a.k);}
il double crossy(const line&a,const line&b){return a.b+crossx(a,b)*a.k;};
struct bag{
	std::set<line>st;
	double ans;
	il vd insert(line x){
		auto it=st.lower_bound(x);line A,B;
		if(it!=st.end()){
			if(it->k==x.k)
				if(it->b>=x.b)return;
				else st.erase(it);
			else if(it!=st.begin()){
				B=*it;A=*--it;
				if(x.get(crossx(A,B))<=crossy(A,B))return;
			}
		}
		//printf("insert %lld %lld\n",x.k,x.b);
		//for(auto i:st)printf("%lld %lld\n",i.k,i.b);
		//puts("");
		while(1){
			it=st.lower_bound(x);
			if(it==st.begin())break;
			if(--it==st.begin())break;
			A=*it;B=*--it;
			if(crossx(A,x)<crossx(A,B))st.erase(++it);
			else break;
		}
		while(1){
			it=st.lower_bound(x);
			if(it==st.end())break;
			A=*it;
			if(++it==st.end())break;
			B=*it;
			if(crossx(A,x)>crossx(A,B))st.erase(--it);
			else break;
		}
		st.insert(x);
		//for(auto i:st)printf("%lld %lld\n",i.k,i.b);
		//puts("\n");
	}
	il ll query(ll i){
		while(st.size()>1){
			line a=*st.begin(),b=*++st.begin();
			if(crossx(a,b)<i)st.erase(st.begin());
			else break;
		}
		if(st.empty())return -1e18;
		else{line a=*st.begin();
			return a.get(i);}
	}
}bag[1000010];
int nowg[1000010],realg[1000010],c[1000010];
std::pair<int,int>op[2000010];
line line[1000010];
signed main(){
	int p;n=gi(),m=gi(),p=gi(),N=n*m;
	for(int i=1;i<=m;++i)a[i]=-gi();
	for(int i=1;i<=m;++i)b[i]=-gi();
	for(int i=1;i<=n;++i)scanf("%s",s+1+m*(i-1));
	std::reverse(s+1,s+N+1);
	SA::getSA();
	for(int i=1;i<=m;++i){
		line[i].k=a[i];line[i].b=dp[i-1]-1ll*a[i]*(i-1)+b[i];
		for(int j=1;j<=n;++j)c[j]=SA::rk[N-(i+(j-1)*m)+1];
		std::sort(c+1,c+n+1);
		for(int j=1;j<n;++j)nowg[j]=std::max(0,i-SA::LCP(c[j],c[j+1]));
		int k=0;
		for(int j=1;j<n;++j)op[++k]={nowg[j],1};
		std::sort(op+1,op+k+1,std::greater<std::pair<int,int>>());
		op[++k]={0,0};
		int sum=1;
		op[0].first=i;
		for(int j=1;j<=k;++j){
			if(op[j].first!=op[j-1].first&&sum>realg[op[j-1].first])
				for(int k=op[j-1].first;k>op[j].first;--k){
					if(realg[k]==sum)break;
					bag[realg[k]=sum].insert(line[k]);
				}
			sum+=op[j].second;
		}
		dp[i]=-1e18;
		for(int j=1;j<=n;++j)
			dp[i]=std::max(dp[i],bag[j].query(i)+1ll*p*j);
		//printf("dp[%d]=%lld\n",i,dp[i]);
	}
	printf("%lld\n",dp[m]);
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 935ms, 内存消耗: 235596K, 提交时间: 2019-07-01 22:35:21

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
int gi(){
	int x=0,w=1;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')w=0,ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}

const int N=1e6+5;
int n,m,root,tot,ch[N][26],dep[N],sz[N],p[N],rt[N],ls[N<<2],rs[N<<2];char str[N];
vector<int>pos[N];long long val,A[N],B[N],k[N<<2],b[N<<2],dp[N];
void insert(){
	for(int i=1,x=root;i<=m;++i){
		int c=str[i]-'a';
		if(!ch[x][c])ch[x][c]=++tot,++sz[dep[tot]=i];
		x=ch[x][c];
	}
}
int merge(int x,int y){
	if(!x||!y)return x|y;
	--sz[dep[x]];
	for(int i=0;i<26;++i)ch[x][i]=merge(ch[x][i],ch[y][i]);
	return x;
}
void solve(int x){
	pos[x].resize(n+1);
	for(int i=1;i<=n;++i){
		if(sz[m]<i){pos[x][i]=0;continue;}
		int l=2,r=x,res=1;
		while(l<=r){
			int mid=l+r>>1;
			if(sz[m-mid+1]>=i)res=mid,l=mid+1;
			else r=mid-1;
		}
		pos[x][i]=res;
	}
}
void build(int &x,int l,int r){
	x=++tot;b[x]=-1ll<<60;if(l==r)return;
	int mid=l+r>>1;build(ls[x],l,mid);build(rs[x],mid+1,r);
}
void modify(int x,int l,int r,long long _k,long long _b){
	long long vl1=k[x]*l+b[x],vr1=k[x]*r+b[x];
	long long vl2=_k*l+_b,vr2=_k*r+_b;
	if(vl1<=vl2&&vr1<=vr2){k[x]=_k;b[x]=_b;return;}
	if(vl1>=vl2&&vr1>=vr2)return;
	int mid=l+r>>1;
	if(k[x]*mid+b[x]<_k*mid+_b)swap(k[x],_k),swap(b[x],_b);
	modify(ls[x],l,mid,_k,_b);modify(rs[x],mid+1,r,_k,_b);
}
long long query(int x,int l,int r,int p){
	long long res=k[x]*p+b[x];
	if(l==r)return res;
	int mid=l+r>>1;
	if(p<=mid)return max(res,query(ls[x],l,mid,p));
	else return max(res,query(rs[x],mid+1,r,p));
}
int main(){
	n=gi();m=gi();val=gi();root=tot=1;
	for(int i=1;i<=m;++i)A[i]=gi();
	for(int i=1;i<=m;++i)B[i]=gi();
	for(int i=1;i<=n;++i)scanf("%s",str+1),reverse(str+1,str+m+1),insert();
	solve(m);
	for(int i=1;i<m;++i){
		int x=ch[root][0];
		for(int j=1;j<26;++j)x=merge(x,ch[root][j]);
		root=x;solve(m-i);
	}
	tot=0;for(int i=1;i<=n;++i)build(rt[i],1,m);
	for(int i=1;i<=m;++i){
		dp[i]=-1ll<<60;
		for(int j=1;j<=n;++j){
			while(p[j]<pos[i][j]){
				int x=++p[j];
				modify(rt[j],1,m,-A[x],dp[x-1]+A[x]*(x-1)-B[x]);
			}
			dp[i]=max(dp[i],query(rt[j],1,m,i)+val*j);
		}
	}
	printf("%lld\n",dp[m]);return 0;
}

详情