• API
• FAQ
• Tools
• Archive
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.

Top