水分过大
查看原帖
水分过大
1266289
xiaoxiao_liang楼主2025/1/18 14:44

从隔壁tctm的oj过来的

#include<bits/stdc++.h>
using namespace std;
long long n,m;
long long v[100010],s[100010];
bool dp[500010];
long long maxn,t[100010],sum=0;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>v[i]>>s[i];
		sum+=v[i]*s[i];
	}
	dp[0]=1;
	for(int i=1;i<=m;i++){cin>>t[i];maxn=max(maxn,t[i]);}
	for(int i=1;i<=n;i++){
		for(int j=min(maxn,sum);j>=v[i];j--){
			for(int k=1;k<=s[i] && k*v[i]<=j;k++){
				dp[j]=dp[j]||dp[j-k*v[i]];
				if(dp[j]) break;
			}
		}
	}
	for(int i=1;i<=m;i++){
		if(t[i]>sum) cout<<"No";
		else if(dp[t[i]]) cout<<"Yes";
		else cout<<"No";
		cout<<endl;
	}
	return 0;
}

其中第二十二行在谷不加也能ac 所以谷的数据有点小 (仅代表个人观点,侵权自删)

2025/1/18 14:44
加载中...