Submission #6912618

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
typedef long long ll;

int main() {
  ll N,W;
  cin >> N >> W;
  ll INF = 100000000000000;
  vector<ll> weight(110);
  vector<ll> value(110);
  vector<vector<ll>> dp(110, vector<ll>(100100,INF));
  
  for(ll i = 0;i<N;i++){
    cin >> value[i];
    cin >> weight[i];
  }
dp[0][0] = 0;
  rep(i,N){
    rep(sum_v,100100){
      if(sum_v-value[i] >=0){
        chmin(dp[i+1][sum_v],dp[i][sum_v-value[i]]+weight[i]);
      }
      chmin(dp[i+1][sum_v],dp[i][sum_v]);
    }
  }
    ll res = 0;
  for(ll sum_v = 0;sum_v<100100;sum_v++){
    if(dp[N][sum_v]<=W){
      res = max(res,sum_v);
    }
  }
  
cout << res << endl;
  
}

Submission Info

Judge Result