Problem link: https://acm.timus.ru/problem.aspx?space=1&num=1522

In this problem all you have to do is to come up with clever sorting comparator.

This one is fine:

int sign(int x) { return x < 0 ? -1 : x > 0; }
struct info_t {
  int a, b, c, id;
  int get() const {
    if (a <= c) {
      return (a + b);
    } else {
      return -(b + c);
    }
  }
  bool operator <(const info_t &y) const {
    int xg = this->get(), yg = y.get();
    if (sgn(xg) != sgn(yg)) {
      return sgn(xg) > sgn(yg);
    } else {
      return xg < yg;
    }
  }
};

After sorting the answer is just:

int64_t ta = 0, tb = 0, tc = 0;
for (const info_t &toy : toys) {
  ta += toy.a;
  tb = max(ta, tb) + toy.b;
  tc = max(tb, tc) + toy.c;
}
// output tc

I don't understand how to prove all details of this solution, and hence my request.

I started trying to work out different cases. If we knew that in the first group the system of inequalities $$$a_i \lt b_j \lt c_k$$$ held, then the time needed to produce toy $$$T_2$$$ after toy $$$T_1$$$, with empty machines, would amount to $$$a_1 + b_1 + c_1 + c_2$$$; if we tried to produce $$$T_1$$$ after $$$T_2$$$, that is reverse the order, the time would equal to $$$a_2 + b_2 + c_1 + c_2$$$. If we were to compare two values we'd understand why we need to compare using $$$a_i + b_i$$$; $$$cost(T_1, T_2) - cost(T_2, T_1) = a_1 + b_1 - a_2 - b_2$$$.

Similarly, if we knew that the second group satisfies $$$a_i \gt b_j \gt c_k$$$, we could get that $$$cost(T_1, T_2) = a_1 + a_2 + b_2 + c_2$$$; and $$$cost(T_1, T_2) - cost(T_2, T_1) = b_2 + c_2 - b_1 - c_1$$$; and that's why the second group is sorted in descending order.

There are two other possible cases inside a single group: $$$b_i \lt a_j \lt c_k$$$ and $$$b_i \lt c_j \lt a_k$$$. In both cases the cost seems to be $$$cost(T_1, T_2) = a_i + \max(b_1 + c_1, a_2 + b_2) + c_2$$$. I don't know how to prove the comparator works for these. And there doesn't seem to be a nice way to get a comparator by subtracting costs. Simply comparing two costs $$$cost(T_1, T_2)$$$ and $$$cost(T_2, T_1)$$$ in this case—and in general—is not a strict weak ordering, and thus undefined behavior for sorting (this can get AC though).

I also don't know why we must append second group to the first. Why should there be these two groups? And why exactly it's better for the second group to follow the first? If we process the second group before the first, the cost is not optimal even in the test sample.