<p>You are given two <strong>0-indexed</strong> integer arrays,&nbsp;<code>cost</code> and <code>time</code>, of size <code>n</code> representing the costs and the time taken to paint <code>n</code> different walls respectively. There are two painters available:</p>

<ul>
	<li>A<strong>&nbsp;paid painter</strong>&nbsp;that paints the <code>i<sup>th</sup></code> wall in <code>time[i]</code> units of time and takes <code>cost[i]</code> units of money.</li>
	<li>A<strong>&nbsp;free painter</strong> that paints&nbsp;<strong>any</strong> wall in <code>1</code> unit of time at a cost of <code>0</code>. But the&nbsp;free painter can only be used if the paid painter is already <strong>occupied</strong>.</li>
</ul>

<p>Return <em>the minimum amount of money required to paint the </em><code>n</code><em>&nbsp;walls.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> cost = [1,2,3,2], time = [1,2,3,2]
<strong>Output:</strong> 3
<strong>Explanation:</strong> The walls at index 0 and 1 will be painted by the paid painter, and it will take 3 units of time; meanwhile, the free painter will paint the walls at index 2 and 3, free of cost in 2 units of time. Thus, the total cost is 1 + 2 = 3.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> cost = [2,3,4,2], time = [1,1,1,1]
<strong>Output:</strong> 4
<strong>Explanation:</strong> The walls at index 0 and 3 will be painted by the paid painter, and it will take 2 units of time; meanwhile, the free painter will paint the walls at index 1 and 2, free of cost in 2 units of time. Thus, the total cost is 2 + 2 = 4.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= cost.length &lt;= 500</code></li>
	<li><code>cost.length == time.length</code></li>
	<li><code>1 &lt;= cost[i] &lt;= 10<sup>6</sup></code></li>
	<li><code>1 &lt;= time[i] &lt;= 500</code></li>
</ul>

class Solution {
public:
  // if the paid guy paints x walls
  // the free guy should paint n - x walls
  // what's the minimum cost to paint x walls so that their time is at least (n - x)?
  int solve1(vector<int>& cost, vector<int>& time) {
    const int inf = 1e9;
    const int n = cost.size();

    for (int i = 0; i < n; ++i) {
      time[i] = min(time[i], n);
    }

    vector<int> order(n, 0);
    for (int i = 0; i < n; ++i) {
      order[i] = i;
    }

    sort(order.begin(), order.end(), [&](int l, int r) -> bool {
      return cost[l] < cost[r];
    });

    vector<vector<pair<int, int>>> dp(n + 1);
    dp[0].emplace_back(0, 0);

    vector<pair<int, int>> next;
    const auto insert = [&](int t, int c) -> void {
      while (!next.empty() && next.back().second >= c) {
        next.pop_back();
      }

      next.emplace_back(t, c);
    };

    for (int i = 0; i < n; ++i) {      
      for (int take = i + 1; take > 0; --take) {
        auto& current = dp[take];
        auto& prev = dp[take - 1];
        int cur_p = 0;

        next.clear();
        for (const auto& prev : dp[take - 1]) {
          int prev_time = prev.first;
          int prev_cost = prev.second;

          int cur_time = min(prev_time + time[order[i]], n);
          int cur_cost = prev_cost + cost[order[i]];

          // find first in current that has time > cur_time.
          while (cur_p < current.size() && current[cur_p].first < cur_time) {
            next.emplace_back(current[cur_p]);
            cur_p += 1;
          }

          // if it's the end, add in the end, stop, update the beginning of the array.
          if (cur_p == current.size()) {
            insert(cur_time, cur_cost);
          } else {
            // if there is a record with same time
            // if it's cost bigger, then we can update it, and then we'll need to update the prefix
            // if it's cost is the same, do nothing
            // if it's cost is smaller, do nothing
            if (current[cur_p].first == cur_time) {
              if (current[cur_p].second >= cur_cost) {
                insert(cur_time, cur_cost);
                cur_p += 1;
              }
            } else {
              // if there is no record with the same time, but there is a record with bigger time
              // if it's cost is bigger, then we need to insert
              // if it's cost is the same, do nothing
              // if it's cost is smaller, do nothing
              if (current[cur_p].second >= cur_cost) {
                insert(cur_time, cur_cost);
              }
            }
          }
        }

        while (cur_p < current.size()) {
          insert(current[cur_p].first, current[cur_p].second);
          cur_p += 1;    
        }

        current.swap(next);
      }
    }

    int ans = inf;
    for (int paid = 1; paid <= n; ++paid) {
      int free = n - paid;
      for (const auto& [t, c] : dp[paid]) {
        if (t >= free) {
          ans = min(ans, c);
        }
      }
    }

    return ans;
  }

  int paintWalls(vector<int>& cost, vector<int>& time) {
    return solve1(cost, time);
  }
};
125312