SHARE
TWEET

Untitled

a guest Apr 21st, 2018 113 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. long long dp[1000001];
  4. int main() {
  5.     int n,k;
  6.     cin >> n >> k;
  7.     long long a[100001],b[100001];
  8.     for(int i = 1; i <= n; i++){
  9.         cin >> b[i] >> a[i];
  10.         b[i] = b[i] - a[i];
  11.     }
  12.     dp[0] = 1;
  13.     for(int i = 1; i <= n; i ++){
  14.         for(int j = k - a[i]; j >= 0; j--){
  15.             if(dp[j] > 0){
  16.                 dp[j + a[i]] = max(dp[j] + b[i], dp[j + a[i]]);
  17.             }
  18.         }
  19.     }
  20.     sort(dp,dp + 1 + k);
  21.     cout << dp[k] - 1;
  22. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top