всесиб 3

/*Задача 3. Вадим и лимонад
Имя входного файла: input.txt
Имя выходного файла: output.txt
Ограничение по времени: 2 секунды, для Java — 4 секунды
Ограничение по памяти: 768 мегабайт
«If life gives you lemons, make
lemonade!»
— «Если судьба кормит вас
сплошными лимонами, то ищите
способ сделать из них лимонад. . . »
— Народная мудрость
Знаменитый блогер-программист Вадим очень любит лимонад. Он является активным
сторонником здорового образа жизни, и поэтому может каждый день выпивать полностью
только одну бутылку лимонада — ни больше, ни меньше. Однако, за Вадимом было замечено
странное свойство: выпив 𝑉 нанолитров лимонада качества 𝑞, на следующий день ему хочется
выпить 𝑉 · 𝑞 нанолитров. Причем, чтобы утолить жажду в первый день, Вадиму достаточно
выпить любое ненулевое количество лимонада.
Фан-клуб Вадима решил подарить ему набор бутылок с лимонадом такой, чтобы Вадим
смог как можно дольше не испытывать жажды. При этом его фанаты хотят потратить как
можно меньше денег.
В магазине продаются пустые бутылки без лимонада. Для каждой бутылки известны ее
объем и стоимость. По счастливой случайности у одного из членов фан-клуба есть знакомый
на фабрике лимонада. Поэтому за лимонад не придется платить, однако весь лимонад будет
одинакового качества, и это качество может быть заказано производителям фан-клубом.
Качество лимонада всегда измеряется положительным числом, но, возможно, не целым.
Так как бутылок в магазине может быть много, то вас попросили написать программу,
определяющую самую дешёвую последовательность бутылок, при помощи которой Вадим
сможет максимально долго утолять жажду.
Формат входных данных
В первой строке входного файла записано число 𝑁 — количество бутылок в магазине
(1 6 𝑁 6 5000).
Вторая строка содержит объемы бутылок в магазине. Это 𝑁 целых положительных чисел,
где 𝑉𝑖 — объем 𝑖-й бутылки (1 6 𝑉𝑖 6 1018
, 1 6 𝑖 6 𝑁).
В третью строку записаны, соответственно, стоимости этих бутылок. Это также 𝑁 целых
положительных чисел, где 𝐶𝑖 — стоимость 𝑖-й бутылки (1 6 𝐶𝑖 6 106
, 1 6 𝑖 6 𝑁).
Формат выходных данных
В первую строку выходного файла нужно вывести два числа — количество бутылок и стоимость самого дешёвого набора бутылок, при помощи которого Вадим сможет максимально
долго утолять жажду.
Во вторую строку нужно выведите номера бутылок такого набора в порядке, в котором
Вадим их должен пить.
Если таких наборов несколько, выведите любой.
Страница 6 из 14
Всесибирская открытая олимпиада школьников по информатике
Отборочный очный этап, 9-11 классы, 27 ноября 2022 г.
Система оценки
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
Подзадача Баллы Ограничения Необходимые подзадачи
1 0 Тесты из условия
2 15 1 6 𝑁 6 20; 1 6 𝑉𝑖 6 109 1
3 35 1 6 𝑁 6 500; 1 6 𝑉𝑖 6 109 1, 2
4 40 1 6 𝑉𝑖 6 109 1, 2, 3
5 10 Нет дополнительных ограничений 1, 2, 3, 4
Примеры
input.txt output.txt
5
1 7 4 8 2
1 2 3 4 5
4 13
1 5 3 4
4
1 1 2 2
10 8 7 7
2 14
3 4
Замечание
Качество лимонада может быть меньшим 1, тогда на следующий день Вадиму захочется
выпить меньше лимонада, чем в текущий.*/

#include<iostream>
#include<vector>
#include<stdint.h>
#include<fstream>
#include<string>
#include<algorithm>
#define all(container) (container.begin(), container.end())
#define fors(counter, start, finish) for (int counter = start; counter < finish; ++counter);
#define forb(counter, start, finish) for (int counter = start; counter >= finish; --counter);
#define vec(type) std::vector<type>
#define dvec(type) std::vector<std::vector<type>>
#define ll int64_t
//#define fin std::cin
//#define fout std::cout

struct boutle {
    double v;
    double c;
};

int n;
std::pair<int, int> ans;
std::vector<boutle> b;
vec(int) res, dres;
vec(bool) done;
void per(double& q, double v, int count, int dol) {
    res.push_back(v);
    double temp = b[v].v * q;
    for (int i = 0; i < n; ++i) {
        if (b[i].v == temp && !done[i]) {
            done[i] = !done[i];
            per(q, i, count + 1, dol + b[i].c);
            done[i] = !done[i];
        }
    }
    if (ans.first < count || (ans.first == count && ans.second > dol)) {
        ans.first = count; ans.second = dol;
        dres = res;
    }
    res.resize(res.size() - 1);
    return;
}

int main() {
    std::ifstream fin("input.txt");
    std::ofstream fout("output.txt");
    ans.first = 0; ans.second = 1000000000;
    fin >> n;
    b.resize(n); done.resize(n);
    for (int i = 0; i < n; ++i)
        fin >> b[i].v;
    for (int i = 0; i < n; ++i)
        fin >> b[i].c;
    for (int i = 0; i < n; ++i) {
        if (!done[i]) {
            done[i] = !done[i];
            res.push_back(i);
            for (int j = i + 1; j < n; ++j) {
                if (!done[j]) {
                    done[j] = !done[j];
                    double q = b[j].v / b[i].v;
                    per(q, j, 2, b[i].c + b[j].c);
                    done[j] = !done[j];
                }
            }
            done[i] = !done[i];
            res.resize(res.size() - 1);
        }
    }
    fout << ans.first << " " << ans.second << std::endl;
    for (int i = 0; i < dres.size(); ++i)
        fout << dres[i] + 1 << " ";
    return 0;
}