维生素B，少熬夜 感觉比今年T1简单

0 pts

巴巴博一

10 pts

在100分代码上将 j&1 改为 j

? pts

O(n*m^2^) (shawanyi)

90 pts

在100代码上将答案 $\sum_1^m f_{n,i}$ 改为 $f_{n,m}$

100 pts

Q1:最大值最小考虑二分答案,dp 转移显然，答案记为$ans$

Q2：定义 $pre_{i}$ 表示最大的 $j$ 满足 $\sum_{j+1}^i L_{k} <= ans$ ，预处理节省老哥

直接想切断有些绕，其实问题就是分为m+1段

设$dp_{i,j}$ 表示前 i 个数分为了j 段的方案数：

$f_{i,j} = \sum_{pre[i]}^{i-1} f_{l,j-1}$

（就这调了1h，维生素B）

前缀和优化即可

#include<bits/stdc++.h>
#define int long long 
using namespace std;
int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0' || c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0' && c<='9') x=x*10+c-'0',c=getchar();
	return x*f; 
}
void write(int x){
	if(x<0) putchar(' '),x=-x;
	if(x<10) putchar(x+'0');
	else write(x/10),putchar(x%10+'0');
}
int n,m,p,L[500010],sum[500010],dp[500010],pre[500010],f[500010][2],tmp[500010][2];
bool check(int x){
	if(L[1]>x) return 0;
	memset(dp,0,sizeof(dp));
	dp[0]=-1;
	for(int i=2;i<=n;i++){
		int l=0,r=i-1,mid;
		if(L[i] > x) return 0;
		while(l<r){
			mid=l+r>>1;
			if(sum[i]-sum[mid]<=x) r=mid;
			else l=mid+1;
		}
		dp[i] = dp[l]+1;
	}
	return (dp[n] <= m);
}
signed main(){
//	freopen("ex.in","r",stdin);
	n=read(),m=read(),p=read(); 
	for(int i=1,x;i<=n;++i) L[i]=read(),sum[i]=sum[i-1]+L[i];
	int l=0,r=1e9,mid;
	while(l<r) {
		mid=l+r>>1;
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	write(l);
	putchar(' ');
	int ans=l, cnt=0;
	for(int i=1;i<=n;i++){
		l=0,r=i-1,mid;
		while(l<r){
			mid=l+r>>1;
			if(sum[i]-sum[mid]<=ans) r=mid;
			else l=mid+1;
		}
		pre[i]=l;
	}
	if(m==0){
		write(1);
		return 0;
	}
	for(int i=1;i<=n;i++) {
		if(cnt+L[i]>ans) break;
		f[i][1]=1;
		cnt+=L[i];
	}
	cnt=0;
	for(int j=2;j<=m+1;j++){
		for(int i=1;i<=n;i++){
			tmp[i][(j-1)&1] = tmp[i-1][(j-1)&1] + f[i][(j-1)&1];
			while(tmp[i][(j-1)&1] >= p) tmp[i][(j-1)&1]-=p;
		}			
		for(int i=1;i<=n;i++){
			if(pre[i]==0) f[i][j&1] =   tmp[i-1][(j-1)&1];
			else f[i][j&1] =  tmp[i-1][(j-1)&1] - tmp[pre[i]-1][(j-1)&1]+p;
			while(f[i][j&1]>=p) f[i][j&1] -=p;
			//cout<< i<<' '<<j<<' '<<f[i][j&1]<<'\n';
		}	
		cnt+=f[n][j&1];
		cnt%=p;
	}
	write(cnt);
	return 0;
}

滚动数组 $避免MLE 避免MLE 避免MLE$