title: Assign the work for 2 people so that the time is minimum
body: <p><strong>Question:</strong></p>
  <p>There are <strong>N</strong> works that needs to be assigned for 2 people. Person <strong>A</strong> can finish work <em>i</em> in <em><strong>a[i]</strong></em> time, person <strong>B</strong> can finish work <em>i</em> in <em><strong>b[i]</strong></em> time.</p>
  <p>Each work can only be assigned to 1 person. After the works are assigned, each person will do their works seperately.</p>
  <p>The overall time will be the larger of the total time taken by the 2 people.</p>
  <p><em><strong>Find a way to assign the work so that the Overall Time is minimum.</strong></em></p>
  <p><strong>Example:</strong></p>
  <pre><code>N = 6
  a[] = 10 100 30 50 50 80
  b[] = 100 30 40 40 60 90
  
  Answer: 130
  
  Explaination:
  
  Person A do work 1, 3, 6 -&gt; total time: 120
  Person B do work 2, 4, 5 -&gt; total time: 130
  
  Overall time: 130
  </code></pre>
  <p><strong>Constrants:</strong></p>
  <pre><code>N &lt;= 100
  a[i], b[i] &lt;= 30.000
  </code></pre>
  <p><strong>My take</strong></p>
  <p>I tried solving it with dynamic-programming, more specifically: <code>DP[i][p][c]</code>
  With <strong>i</strong> is the number of works done so far, <strong>p</strong> is total time of person A so far, <strong>c</strong> is total time of person B so far. For each i, we can try to give the work to either person A or B, then save the best answer in <code>DP[i][p][c]</code> so we dont have to recalculate it.</p>
  <p>But <strong>p</strong> and <strong>c</strong> can get up to 3.000.000, so I tried to shrink it to <code>DP[i][max(p,c)]</code></p>
  <p>The code below gives the right answer for the example case, and some other case I generated:</p>
  <pre><code>int n, firstCost[105], secondCost[105];
  int dp[105][300005];
  
  int solve(int i, int p, int c){
      if(i &gt; n) return max(p, c);
  
      int &amp;res = dp[i][max(p, c)];
      if(res != -1) return res;
  
      res = INT_MAX;
      int tmp1 = solve(i+1, p + firstCost[i], c);
      int tmp2 = solve(i+1, p, c + secondCost[i]);
  
      res = min(tmp1, tmp2);
      return res;
  }
  
  int main(){
      // input...
      cout &lt;&lt; solve(1, 0, 0);
  }
  </code></pre>
  <p>But when I submited it, it gives the wrong anwer to this case:</p>
  <pre><code>20
  4034 18449 10427 4752 8197 7698 17402 16164 12306 5249 19076 18560 16584 18969 3548 11260 6752 18052 14684 18113
  19685 10028 938 10379 11583 10383 7175 4557 850 5704 14156 18587 2869 16300 15393 14874 18859 9232 6057 3562
  </code></pre>
  <p>My output was <code>77759</code> but the answer is suppose to be <code>80477</code>.</p>
  <p>I don't know what I did wrong, is there anyway to imrpove my solution?</p>
  <p><strong>P/S:</strong></p>
  <p><a href="http://lequydon.ntucoder.net/Problem/Details/6282" rel="nofollow noreferrer">Here's the original problem</a>, the page is in Vietnamese, you can create an account and submit there</p>