8-liner C++ 42ms beat 98% greedy algorithm (detailed explanation)
Key Observation: \n1. The more capital W you have now, the more maximum capital you will eventually earn.\n2. Working on any doable project with positive P[i] >
**Key Observation:** \n1. The more capital `W` you have now, the more maximum capital you will eventually earn.\n2. Working on any doable project with positive `P[i] > 0` increases your capital `W`.\n3. Any project with `P[i] = 0` is useless and should be filtered away immediately (note that the problem only guarantees all inputs non-negative).\n\nTherefore, always work on the most profitable project `P[i]` first as long as it is doable until we reach maximum `k` projects or all doable projects are done.\n\nThe algorithm will be straightforward:\n1. At each stage, split projects into two categories:\n   * "doables": ones with `C[i] <= W` (store `P[i]` in `priority_queue<int> low`)\n   * "undoables": ones with `C[i] > W` (store `(C[i], P[i])` in `multiset<pair<int,int>> high`)\n2. Work on most profitable project from `low` (`low.top()`) first, and update capital `W += low.top()`.\n3. Move those previous undoables from `high` to doables `low` whose `C[i] <= W`.\n4. Repeat steps 2 and 3 until we reach maximum `k` projects or no more doable projects.  \n```\n    int findMaximizedCapital(int k, int W, vector<int>& P, vector<int>& C) {\n      priority_queue<int> low;      // P[i]'s within current W\n      multiset<pair<int,int>> high; // (C[i],P[i])'s' outside current W\n      \n      for (int i = 0; i < P.size(); ++i) // initialize low and high\n        if(P[i] > 0) if (C[i] <= W) low.push(P[i]); else high.emplace(C[i], P[i]);\n    \n      while (k-- && low.size()) { \n        W += low.top(), low.pop(); // greedy to work on most profitable first\n        for (auto i = high.begin(); high.size() && i->first <= W; i = high.erase(i)) low.push(i->second);\n      }\n      return W;\n    }\n```
['Greedy', 'C++']