Камни. Разбить их на две кучи таким образом, чтобы веса куч отличались не более чем в 2 раза

#include <iostream>
#include <vector>
#include <numeric>   // для std::accumulate
#include <algorithm> // для std::min / std::max
using namespace std;
 
/*
   Функция восстанавливает решение (какие камни входят в подмножество, дающее сумму target),
   опираясь на вспомогательный массив dp[][], где dp[i][j] = true, если возможно
   получить сумму j первыми i камнями.
*/
vector<int> reconstructSubset(const vector<int>& stones,
                              const vector<vector<bool>>& dp,
                              int target)
{
    vector<int> subset;
    int i = (int)stones.size(); // идём с конца
    int j = target;
 
    while(i > 0 && j >= 0)
    {
        // Если dp[i][j] == true и dp[i-1][j] == false, значит камень i вошёл в подмножество
        if (dp[i][j] && !dp[i-1][j])
        {
            subset.push_back(stones[i-1]);
            j -= stones[i-1];
        }
        // Двигаемся к i-1
        i--;
    }
    return subset;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int N;
    cin >> N;
 
    vector<int> stones(N);
    for(int i = 0; i < N; i++) {
        cin >> stones[i];
    }
 
    // 1. Считаем сумму
    long long totalSum = 0;
    for(int w : stones) {
        totalSum += w;
    }
 
    // Если сумма = 0 (все камни весят 0, либо нет камней) – частный случай
    if (totalSum == 0) {
        // Тогда обе кучи "весят" 0, это trivially удовлетворяет условию.
        // Но посмотрим, что требовалось: возможно, это тривиально решаемо.
        cout << "All stones are zero or no stones at all. Two piles both have weight 0.\n";
        return 0;
    }
 
    // 2. Вычислим нижнюю и верхнюю границы
    //    (преобразуем в int с учётом округлений)
    long long lowBound  = (totalSum + 2) / 3;  // ceil(S/3)  (+2 - "лайфхак" при целочисленном делении)
    long long highBound = totalSum / 2;       // floor(S/2) (округление вниз)
 
    // Если lowBound > highBound, значит [S/3, S/2] — пустой диапазон, решения нет
    if (lowBound > highBound) {
        cout << "Impossible\n";
        return 0;
    }
 
    // 3. Стандартный метод Subset-Sum (динамическое программирование)
    //    Пусть dp[i][j] = true, если подмножество из первых i камней может дать сумму j.
    //    Размерность: dp[N+1][totalSum+1].
    //    В реальной задаче, если totalSum большое, это может быть слишком затратно по памяти.
    //    Тогда ищут способы оптимизировать. Но для демонстрации идеи – подойдёт.
 
    // Инициализируем dp
    vector<vector<bool>> dp(N+1, vector<bool>(totalSum+1, false));
    dp[0][0] = true; // сумму 0 можно получить, не беря ни одного камня
 
    // Заполнение
    for(int i = 1; i <= N; i++) {
        int w = stones[i-1]; // вес i-го камня (индексация i-1)
        for(long long sumVal = 0; sumVal <= totalSum; sumVal++) {
            // Не берём камень i
            dp[i][sumVal] = dp[i-1][sumVal];
            // Берём камень i (если возможно)
            if (sumVal - w >= 0 && dp[i-1][sumVal - w]) {
                dp[i][sumVal] = true;
            }
        }
    }
 
    // 4. Ищем любую сумму T в [lowBound, highBound], для которой dp[N][T] = true
    //    Если находим – восстанавливаем решение.
    long long foundT = -1;
    for(long long t = lowBound; t <= highBound; t++) {
        if (dp[N][t]) {
            foundT = t;
            break;
        }
    }
 
    if (foundT < 0) {
        // Не нашли подходящей суммы
        cout << "Impossible\n";
    } else {
        // 5. Восстановим подмножество камней, дающее сумму foundT
        vector<int> subset = reconstructSubset(stones, dp, (int)foundT);
 
        // Соберём это подмножество в "кучу1", остальные камни – "куча2"
        // Для наглядности создадим флаги used[]
        vector<bool> used(N, false);
        for (int w : subset) {
            // Но нам надо аккуратно «сопоставить» камни. Если в stones
            // есть повторяющиеся веса, придётся учитывать индексы.
            // Упростим задачу: выполним то же самое «с конца»:
            // Чтобы не усложнять, восполним reconstructSubset так, чтобы возвращать не только веса, а (индекс, вес).
            // Но можно и так: для каждого камня-«кандидата» мы ищем его в subset и помечаем used:
            // Это будет работать корректно только если веса камней различны или subset.size() соответствует кол-ву камней.
            // Для полноты – сделаем более простое соответствие:
            //  -- Ниже "грязный" способ, не оптимальный, но наглядный.
            for (int i = 0; i < N; i++) {
                if (!used[i] && stones[i] == w) {
                    used[i] = true;
                    break;
                }
            }
        }
 
        // 6. Выведем результат. Для проверки выполним подсчёт суммы куч.
        long long sum1 = 0, sum2 = 0;
        cout << "Pile1: ";
        for (int i = 0; i < N; i++) {
            if (used[i]) {
                cout << stones[i] << " ";
                sum1 += stones[i];
            }
        }
        cout << "\nPile2: ";
        for (int i = 0; i < N; i++) {
            if (!used[i]) {
                cout << stones[i] << " ";
                sum2 += stones[i];
            }
        }
        cout << "\n";
 
        // Проверка на соответствие условию (не более чем в 2 раза отличаются)
        // Сами веса куч:
        cout << "Sum of Pile1 = " << sum1 << ", Sum of Pile2 = " << sum2 << "\n";
        long long mx = max(sum1, sum2);
        long long mn = min(sum1, sum2);
        if (mx <= 2LL * mn) {
            cout << "OK: ratio <= 2\n";
        } else {
            cout << "ERROR: ratio > 2 (unexpected)\n";
        }
    }
 
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
 
template<typename T>
std::istream &operator>>(std::istream &in, std::vector<T> &vector) {
    for (T value; in >> value;) {
        vector.emplace_back(value);
    }
    return in;
}
 
template<typename T>
std::ostream &operator<<(std::ostream &out, const std::vector<T> &vector) {
    for (auto i = vector.begin(), end = vector.end(); i != end;) {
        out << *i;
        if (++i != end) {
            out << ", ";
        }
    }
    return out;
}
 
template<typename T, typename OutputIterator1, typename OutputIterator2>
std::pair<T, T> partition(std::vector<T> source, OutputIterator1 heap1, OutputIterator2 heap2) {
    T sum1 = 0;
    T sum2 = 0;
    std::sort(source.begin(), source.end(), std::greater_equal());
    for (auto begin = source.begin(), end = source.end(); begin != end; ++begin) {
        if (sum2 > sum1) {
            *heap1++ = *begin;
            sum1 += *begin;
        } else {
            *heap2++ = *begin;
            sum2 += *begin;
        }
    }
    return {sum1, sum2};
}
 
int main() {
    std::vector<int> stones;
 
    std::cin >> stones;
 
    std::vector<int> heap1, heap2;
    auto result = partition(stones, std::back_inserter(heap1), std::back_inserter(heap2));
 
    std::cout << "Initial heap: " << stones << std::endl
              << "Divided heaps:" << std::endl
              << "Heap 1: " << heap1 << std::endl
              << "Heap 1 sum: " << result.first << std::endl
              << "Heap 2: " << heap2 << std::endl
              << "Heap 2 sum: " << result.second << std::endl;
 
    if ((static_cast<double>(std::max(result.first, result.second)) / std::min(result.first, result.second) >= 2)) {
        std::cout << "Cannot divide in two heaps that are less than two times different." << std::endl;
    }
 
    return 0;
}