всесиб 4

/*Задача 4. Вадим и телефонный звонок
Имя входного файла: input.txt
Имя выходного файла: output.txt
Ограничение по времени: 3 секунды, для Java — 5 секунд
Ограничение по памяти: 256 мегабайт
— Ты опять не выходишь на связь,
Вадим?
Думая о том, что завтра он снова сможет полакомиться любимым лимонадом из очередной бутылки, подаренной фанатами, Вадим услышал телефонный звонок. Вадим взглянул
на телефон — звонит школьный товарищ, с которым он давно не общался, а о многом так
хочется поговорить... Он немедленно схватил трубку, ответил на вызов и ... в ответ услышал лишь шипение. Очевидно — плохая связь. К нему тотчас же нагрянуло воспоминание
из детства, городская легенда, гласившая о том, что якобы, если произнести определенные
слова во время разговора, то связь улучшится.
Вадим откопал у себя старый блокнот, в который он записывал слова, которые, как ему
казалось, улучшают качество связи. Он бегло произнес пару слов из блокнота и, о чудо, связь
улучшилась. После продолжительного разговора ему стало интересно, сколькими способами
он может произнести слова, чтобы увеличить качество связи на некоторое значение. Внутреннее чувство тревоги подсказывает ему, что превосходить некоторый порог может быть
опасно. Ведь всем известно, что лучшее — враг хорошего. Связь может вообще оборваться.
Формат входных данных
В первой строке входного файла записано целое число 𝑁 — количество слов в блокноте
(1 6 𝑁 6 105
).
В следующей строке заданы 𝑁 чисел, каждое из которых означает, на сколько улучшается
связь при произнесении соответствующего слова из блокнота (1 6 𝑎𝑖 6 99, 1 6 𝑖 6 𝑁).
В последней строке записаны два числа 𝐿 и 𝑅 — минимальное значение, на которое
необходимо улучшить качество связи и порог, превосходить который чрезвычайно опасно
(1 6 𝐿 6 𝑅 6 1018).
Формат выходных данных
В выходной файл необходимо вывести одно число — количество различных способов произнести слова из блокнота, чтобы улучшить связь, не превосходя заданный порог.
Поскольку ответ может быть достаточно большим, выведите остаток от деления его на
число 998244353.
Два способа считаются различными, если в некоторый момент времени были произнесены
различные слова.
Система оценки
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
Страница 8 из 14
Всесибирская открытая олимпиада школьников по информатике
Отборочный очный этап, 9-11 классы, 27 ноября 2022 г.
Подзадача Баллы Ограничения Необходимые подзадачи
1 0 Тесты из условия
2 6 1 6 𝑁 6 5; 1 6 𝑎𝑖 6 10; 1 6 𝐿 6 𝑅 6 10 1
3 14 1 6 𝑁 6 100; 1 6 𝑎𝑖 6 99; 1 6 𝐿 6 𝑅 6 100 1, 2
4 12 1 6 𝑁 6 105
; 1 6 𝑎𝑖 6 99; 1 6 𝐿 6 𝑅 6 106
среди 𝑎𝑖 не более 2 различных значений 1
5 18 1 6 𝑁 6 105
; 1 6 𝑎𝑖 6 99; 1 6 𝐿 6 𝑅 6 5 · 104 1, 2, 3
6 20 𝑅 − 𝐿 6 100 1, 2, 3
7 30 Нет дополнительных ограничений 1, 2, 3, 4, 5, 6
Примеры
input.txt output.txt
2
1 2
1 3
6
1
2
3 3
0
2
1 2
1 10
231
Замечание
Пусть в первом примере есть два слова: 𝐴 и 𝐵 соответственно, тогда допустимыми будут
следующие способы: 𝐴, 𝐵, 𝐴𝐴, 𝐴𝐵, 𝐵𝐴, 𝐴𝐴𝐴.
Во втором примере не существует ни одного способа, удовлетворяющего условию*/


#include<iostream>
#include<vector>
#include<stdint.h>
#include<fstream>
#include<string>
#include<algorithm>
#include<map>
#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

int main() {
    std::ifstream fin("input.txt");
    std::ofstream fout("output.txt");
    ll n, min, max, ans = 0;
    fin >> n;
    vec(int) w(n);
    w.resize(n);
    std::map<ll, ll> res;
    for (int i = 0; i < n; ++i) {
        fin >> w[i];
        res[w[i]]++;
    }
    fin >> min >> max;

    for (std::pair<ll, ll> i : res) {
        for (int j = 0; j < w.size(); ++j) {
            if (w[j] + i.first <= max)
                res[w[j] + i.first] += res[i.first] % 998244353;
        }
    }

    for (std::pair<ll, int> i : res) {
        if (i.first <= max && i.first >= min)
            ans += res[i.first];
    }
    fout << ans << std::endl;
    return 0;
}