SHARE
TWEET

Trouble of 13-Dots 2

a guest Jul 19th, 2019 67 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 110;
  5. long long m,n;
  6. long long x,y;
  7.  
  8. pair<long long,long long> arr[N];
  9. long long memo[N][10010];
  10.  
  11. long long dp(long long idx,long long money, bool inc)
  12. {
  13.     if(idx == n)
  14.         return 0;
  15.     long long &ret = memo[idx][money];
  16.     if(~ret)
  17.         return ret;
  18.     //cout << idx << " " << money << endl;
  19.     ret = dp(idx+1,money,inc);
  20.     if(money < arr[idx].first) {
  21.     if(abs(m-money)+arr[idx].first>2000 && !inc)
  22.     {
  23.         //cout << m-money << endl;
  24.         money+=200;
  25.         inc = true;
  26.         //cout << arr[idx].first << endl;
  27.  
  28.     }}
  29.     if(money >= arr[idx].first)
  30.         ret = max(ret,dp(idx+1,money-arr[idx].first,inc)+arr[idx].second);
  31.     return ret;
  32. }
  33.  
  34. /*void build(long long idx,long long money, bool inc)
  35. {
  36.  
  37.     long long &ret = memo[idx][money];
  38.  
  39.     if(ret == dp(idx+1,money,inc))
  40.         build(idx+1,money,inc);
  41.     else
  42.     {
  43.         if(money < arr[idx].first) {
  44.         if(abs(m-money)+arr[idx].first>2000 && !inc)
  45.         {
  46.             //cout << m-money << endl;
  47.             money+=200;
  48.             inc = true;
  49.             //cout << arr[idx].first << endl;
  50.  
  51.         }}
  52.         if(money >= arr[idx].first)
  53.         {
  54.             ans.push_back(arr[idx]);
  55.             //cout << arr[idx].first << " " << arr[idx].second << endl;
  56.             build(idx+1,money-arr[idx].first,inc);
  57.         }
  58.     }
  59. }*/
  60.  
  61.  
  62. int main()
  63. {
  64.     ios::sync_with_stdio(0);
  65.     cin.tie(NULL);
  66.     cout.tie(NULL);
  67.  
  68.     #ifndef ONLINE_JUDGE
  69.         freopen("input.txt", "r", stdin);
  70.         freopen("out.txt", "w", stdout);
  71.     #endif // ONLINE_JUDGE
  72.  
  73.     bool first = false;
  74.     while(cin >> m >> n)
  75.     {
  76.         memset(memo,-1,sizeof memo);
  77.         for(int i = 0; i < n; i++)
  78.         {
  79.             cin >> x >> y;
  80.             arr[i] = {x,y};
  81.         }
  82.         sort(arr,arr+n);
  83.         cout << dp(0,m,false) << endl;
  84.     }
  85.  
  86.     return 0;
  87. }
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top