#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
// inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
inline int read(){int x;scanf("%d",&x);return x;}
const int N=5e5+10;
int n,f[N][105],k,mod,a[N];
signed main(){
	// freopen("in.in","r",stdin);freopen("out.out","w",stdout);
	std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
	n=read(),k=read(),mod=read();
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=n;++i)a[i]=(read()+a[i-1])%mod,f[i][1]=a[i];
	for(int j=2;j<=k;++j){
		int min=2e9,minpos=0;
		for(int i=1;i<=n;++i){
			f[i][j]=f[minpos][j-1]+(a[i]-a[minpos]+mod)%mod;
			if(min>f[i][j-1]){
				min=f[i][j-1];minpos=i;
			}
		}
	}
	std::cout<<f[n][k];    
}

#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=5e5+10;
int n,f[105][N],k,mod,a[N],tq[105],th[105];
signed main(){
	// freopen("in.in","r",stdin);freopen("out.out","w",stdout);
	std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
	n=read(),k=read(),mod=read();
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=n;++i)a[i]=(read()+a[i-1])%mod,f[1][i]=a[i];
	for(int j=2;j<=k;++j){
		int min=2e9,minpos=0;
		for(int i=1;i<=n;++i){
			f[j][i]=f[j-1][minpos]+(a[i]-a[minpos]+mod)%mod;
			if(min>f[j-1][i]){
				min=f[j-1][i];minpos=i;
			}
		}
	}
	std::cout<<f[k][n];    
}

rt，上面两份代码除了维度位置都一样。 而第一份代码比第二份慢一秒左右。

CF958C3

慢 快