记录编号	581435	评测结果	AAAAAAAAAA
题目名称	1749.支付宝	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.050 s
提交时间	2023-08-02 22:46:01	内存使用	4.43 MiB

#include <bits/stdc++.h> 
using namespace std;
const int N = 210,M = 20010;
int n,m;
int w[N],c[N],tot,dp[M],ans[N],v[M*10],vv[M*10];
struct made{
	int w,x;
}s[M*10];
void init(){
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)scanf("%d",&w[i]);
    for(int i = 1;i <= n;i++)scanf("%d",&c[i]);
    for(int i = 1;i <= n;i++){
        int p = 1;
        while(c[i] >= p){
            c[i] -= p;
            s[++tot].w = p * w[i];
            s[tot].x = i;
            p <<= 1;
        }
        if(c[i] > 0){
            s[++tot].w = c[i] * w[i];
            s[tot].x = i;
        }
    }
    scanf("%d",&m);
}
void dfs(int x){
	if(x == 0)return;
	int i = v[x];
	ans[s[i].x] += (s[i].w / w[s[i].x]);
	dfs(x-s[i].w);
}
int main(){
    freopen("pay.in","r",stdin);
    freopen("pay.out","w",stdout);
    init();
    memset(dp,0x3f,sizeof(dp));
    dp[0] = 0;
    for(int i = 1;i <= tot;i++){
        for(int j = m;j >= s[i].w;j--){
        	if(dp[j-s[i].w]+1 < dp[j]){
        		dp[j] = dp[j-s[i].w]+1;
        		if(!v[j])v[j] = i;
        		if(j == m)v[j] = i;
			}
        }
    }
    printf("%d\n",dp[m]);
    dfs(m);
    for(int i = 1;i <= n;i++){
    	printf("%d ",ans[i]);
	}
	printf("\n");
    
    return 0;
     
}