POJ(PKU) 1742 Coins

蟻ゲー

以上。

#include <cstdio>
#include <string.h>

using namespace std;
int dp[100003];
int main(){
  
  while(1){
  
  
  int n,m;
  int d[102][2];
  
  
  scanf("%d%d",&n,&m);
  
  if(n == 0)break;
  
  for(int i = 0;i < n;i++){
    scanf("%d",&d[i][0]);
  }
  for(int i = 0;i < n;i++){
    scanf("%d",&d[i][1]);
  }
  

  
  memset(dp, -1 , sizeof(dp));
  dp[0] = 0;
  
  for(int i = 0;i < n;i++){
    for(int j = 0;j <= m;j++){
      if(dp[j] >= 0){
	dp[j] = d[i][1];
      }else if(j < d[i][0] || dp[j - d[i][0]] <= 0){
	dp[j] = -1;
      }else{
	dp[j] = dp[j - d[i][0]] - 1;
      }
    }
  }
  int ans = 0;
  for(int i = m;i >= 1;i--){
    if(dp[i] >= 0){
      ans++;
    }
  }
  
  printf("%d\n",ans);
  }
  
  return 0;
  
}
||<a