Kattis Problem 'Mali' I wrote a solution to the Mali problem on Kattis:


  Given inputs a1, a2, a3, …, an and b1, b2, b3, …, bn, determine n pairings (ai, bj) such that each number in the A sequence is used in exactly one pairing, each number in the B sequence is used in exactly one pairing, and the maximum of all sums ai + bj is minimal.
  
  Input
  
  The first line of input contains a single integer N (1 ≤ N ≤ 100000), the number of rounds.
  
  The next N lines contain two integers A and B (1 ≤ A, B ≤ 100), the numbers given in that round.
  
  Output
  
  The output consists of N lines, one for each round.  Each line should contain the smallest maximal sum for that round.


I'm fairly sure I can get the right answer 100% of the time, but the code exceeds the time limit of one second. I was wondering if you could help me optimize my code to help it run in time, or if you could explain why my code is inefficient.

#include &lt;iostream&gt;
#include &lt;vector&gt;

int main() {
    int x, c = 0, big = 0;
    std::cin &gt;&gt; x;
    std::vector&lt;int&gt; as, bs;
    for (int i = 0; i &lt; x; i++) {
        bool founda = false, foundb = false;
        int a, b;
        std::cin &gt;&gt; a &gt;&gt; b;
        c++;
        if (c == 1) {
            as.push_back(a);
            bs.push_back(b);
        }
        else {
            for (int i = 0; i &lt; c; i++) {
                if (as[i] &lt; a || i == c-1) {
                    as.insert(as.begin()+i, a);
                    founda = true;
                }
                if (bs[i] &lt; b || i == c-1) {
                    bs.insert(bs.begin()+i, b);
                    foundb = true;
                }
                if (founda == true &amp;&amp; foundb == true) 
                    break;
            }
        }
        for (int i = 0; i &lt; c; i++) {
            if (as[i] + bs[c-1-i] &gt; big)
                big = as[i] + bs[c-1-i];
        }
        std::cout &lt;&lt; big &lt;&lt; std::endl;
    }
}
You are storing all of the A and B inputs in sorted vectors, basically doing an insertion sort.  A few observations (two minor, one major):


The if (c == 1) special case should be eliminated.
Flag variables (founda and foundb) suck.  You would be better off writing two separate for loops.
Each time you insert a value, all values beyond the insertion point need to be shifted over to make room for the insertion.  That means that constructing as and bs takes O(N2) time altogether — which is unacceptable, since N can be very large.

However, there are only 100 possible values of A and B.  So, do a counting sort instead, building a histogram with 100 buckets.  That would be a much more efficient way to represent the same information, using O(N) time and a fixed amount of space.