Всем привет. Мне нужна помощь з задачей. Я не знаю как ускорить свой тупой перебор . Вот условие задачи :"Русский бизнесмен Иван Петров закупил в Китае большую партию наручных часов, чтобы продать их на родине за полцены (т.е. в 5 раз дороже, чем они стоили в Китае). Иван столкнулся с проблемой: китайские часы оказались некачественными. Мало того, что часы работали на протяжении всего нескольких часов, пока их не стукнешь, так еще и время подводить неудобно: вращать можно не минутную, а только секундную стрелку, причем, что самое ужасное, только в одну сторону в направлении увеличении времени. Например, для того, чтобы подвести часы на секунду назад, необходимо было сделать более 700 полных оборотов секундной стрелки, на что Иван бы потратил более 10 минут.

Чтобы продать эти часы оптом Ивану необходимо на момент сделки создать видимость того, что часы исправны. Для этого он собирается остановить все часы, установить их на одно и то же время. А перед сделкой ударить по чемодану с часами, чтобы они все дружно пошли.

Помогите Ивану выяснить: какое время на часах лучше установить для того, чтобы Иван потратил как можно меньше времени для того, чтобы подвести все часы.

Входные данные В первой строке входного файла INPUT.TXT содержится натуральное число N – количество часов (N ≤ 50000). В последующих N строках располагаются показания всех часов в формате h:mm:ss, где h – показывает который час, mm – минуты, ss — секунды (1 ≤ h ≤ 12, 0 ≤ mm ≤ 59, 0 ≤ ss ≤ 59).

Выходные данные Выходной файл OUTPUT.TXT должен содержать время, которое нужно установить на всех часах, в формате, указанном выше. В случае неоднозначного ответа выведите наименьшее время." Тест 3 8:19:16 2:05:11 12:50:07 Ответ на Тест 2:05:11 :"https://acmp.ru/asp/do/index.asp?main=task&id_course=2&id_section=15&id_topic=18&id_problem=94" Вот тупой перебор

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
int main() {
    ll n;
    cin >> n;
    vector<ll> times(n);
    for (int i = 0; i < n; i++) {
        ll x, y, z;
        char c;
        cin >> x >> c >> y >> c >> z;
        times[i] = x * 3600 + y * 60 + z;
    }
 
    ll min_sum = 1e18, ans_time = 0;
    for (int i = 0; i < n; i++) {
        ll sum = 0;
        for (int j = 0; j < n; j++) {
            if (times[j] <= times[i]) {
                sum += times[i] - times[j];
            } else {
                sum += times[i] + 12 * 3600 - times[j];
            }
        }
        if (sum < min_sum) {
            min_sum = sum;
            ans_time = times[i];
        }
    }
 
    if (ans_time == 0) ans_time = 12 * 3600;
    printf("%d:%02d:%02d\n", ans_time / 3600, ans_time % 3600 / 60, ans_time % 60);
}