小红不想做完全背包 （hard）（DP）--牛客周赛 Round 39-D

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define inf 1e18
const int mod=1e9+7;
const int N=2005;
//typedef __int128 lll;
//typedef unsigned long long ull;
int n,p;
int a[N],dp[N];
void solve(){
	cin>>n>>p;
	for(int i=0;i<=p;i++) dp[i]=1e18;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i]%=p;
		dp[a[i]]=1;
		for(int j=0;j<p;j++){
			int x=(j-a[i]+p)%p;
			dp[j]=min(dp[j],dp[x]+1);
		}	
	}
	cout<<dp[0];
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int tt=1;
//	cin>>tt;
	while(tt--) solve();
	return 0;
}