SHARE
TWEET

Untitled

a guest May 22nd, 2019 67 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define X first
  2. #define Y second
  3. #define LL long long
  4. #define PB push_back
  5. #define SZ(a) (int)(a.size())
  6. const int MAX = 2 * 100005;
  7. const int INF = 1000 * 1000 * 1000;
  8. LL curProfit = 0;
  9. LL balance;
  10. vector<vector<int> > g(MAX);
  11. long finalBalance(vector<int> cost, vector<int> profit, vector<int> p, int days, int dollars) {
  12.     balance = dollars;
  13.     int n = cost.size();
  14.     set<pair<int , int> > s;
  15.     for(int i = 0; i < n; i++)
  16.     {
  17.         assert(-1 <= p[i] && p[i] < n);
  18.         if(p[i] == -1)
  19.             s.insert({cost[i] , i});
  20.         else
  21.             g[p[i]].PB(i);
  22.     }
  23.     int cnt = 0;
  24.     while(days)
  25.     {
  26.         if(SZ(s))
  27.         {
  28.             int idx = s.begin()->Y;
  29.             if(cost[s.begin()->Y] <= balance)
  30.             {
  31.                 balance -= cost[s.begin()->Y];
  32.                 curProfit += profit[s.begin()->Y];
  33.                 balance += curProfit;
  34.                 days--;
  35.             }
  36.             else
  37.             {
  38.                 if(curProfit <= 0)
  39.                 {
  40.                     balance += curProfit * days;
  41.                     days = 0;
  42.                 }
  43.                 else
  44.                 {
  45.                     LL need = (cost[s.begin()->Y] - balance + curProfit - 1) / curProfit;
  46.                     if(need > days)
  47.                     {
  48.                         balance += days * curProfit;
  49.                         days = 0;
  50.                     }
  51.                     else
  52.                     {
  53.                         days -= need;
  54.                         balance += need * curProfit;
  55.                     }
  56.                 }
  57.             }
  58.             cnt++;
  59.             s.erase({cost[idx] , idx});
  60.             for(auto v : g[idx])
  61.             {
  62.                 s.insert({cost[v] , v});
  63.             }
  64.         }
  65.         else
  66.         {
  67.             balance += curProfit * days;
  68.             days = 0;
  69.         }
  70.     }
  71.     cerr << cnt << endl;
  72.     return balance;
  73. }
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