Допустим что ваша последовательность выполнения квестов выглядит как то так, 1 с с 1 с 1 .... Где единицы соответствуют тому что вы выполнили квесты без бонуса, а с с бонусом. Тогда можно единицы передвинуть в конец, таким образом если вы выполнили квест с бонусом он так и останется с бонусом, если без бонуса вы и в конце его без бонуса выполните. То есть можно решать задачу так что в начале вы выполняете все с бонусом, а в конце без бонуса. Если x[1] ... x[k] это xps полученные с бонусом, а x[k+1] ... x[n] без бонуса, ваш общий xp в конце игры будет c * (x[1] + ... x[k]) + x[k+1] + ... + x[n], где x[1] + ... x[k] + x[k+1] + ... + x[n] фиксированная величина. Значит вам надо максимизировать (c - 1) * (x[1] + ... x[k]) или x[1] + ... x[k].

Заметим если мы выполнили квесты 1 ... k то должны были выполняться следующие неравенства: c * (x[1] + ... + x[k]) < v * d[k] + c * x[k] для всех k. Потому что после выполнения x[k - 1] квеста у вас c * (x[1] + ... + x[k - 1]) xp суммарно и чтобы выполнить теперь k-ый квест с бонусом нужно чтобы ваш xp был не больше v * d[k]. Прибавим в обе части неравенства велечину c * x[k] и получим требуемое.

Заметим теперь что при оптимальной последовательности выполнения квестов величины r[k] = v * d[k] + c * x[k] должны быть упорядочены. Допустим нет и r[k - 1] больше чем r[k]. Тогда поменяем последовательность выполнения что сначала вы выполняете квест k, потом только k - 1 а все остальное остается таким же. Давайте покажем что наши неравенства сохраняться. Могли нарушиться только два из них, такими они были до перестановки (1а)c * (x[1] + ... + x[k - 1]) < r[k - 1] (2а)c * (x[1] + ... + x[k]) < r[k] а стали (1б) c * (x[1] + ... + x[k - 2] + x[k]) < r[k] (2б) c * (x[1] + ... + x[k - 2] + x[k - 1] + x[k]) < r[k - 1] 1б верный потому что r[k] больше суммы всех x[i] по (2а). 2б верный потому что сумма всех меньше r[k] а она меньше по предположению r[k - 1].

И так можно понять что r[k] можно отсортировать и искать решение уже на сортированных r[k]. Как мы будем это делать? Пусть мы закончили квест k (k отсортированы по r[k]) c какой то суммой S. Теперь понятно что если S < v * d[next], для k < next. Мы можем следующим выполнить квест с индексом next. Наша цель в конце иметь наибольшую сумму S, неважно закончив какой квест. То есть по сути у нас есть всевозможные суммы S, желательно для них найти наименьший такой k после выполнения которого у нас будет сумма S. Так чтобы выбор для next был наиболее широким из условия k < next.

Поймем сколько у нас различных сумм может быть. У нас есть ограничения что 1 <= x[i], n <= 2000. То есть если сумма состоит из каких то x и их не больше n, сумма нескольких x[i] не больше 2000 ^ 2. То у нас есть квадратная оценка на количество различных сумм. Наше дальнейшее решение будет основано на том что их значительно меньше, то есть все суммы не будут принимать все возможные значения. Потому что от каждой суммы мы будем смотреть какая следующая сумма может получиться, то есть делать еще один линейный перебор, в итоге получая кубическую оценку. Но решение проходит за 5 сек, когда лимит на задачу 14 сек. Так что все вышло норм.

Давайте сделаем реализацию похожую на dijkstra. У нас есть set<pair<int, int>> в котором мы храним (S, min_index). Что обозначает мы получили сумму S, последним использовав квест индекса не больше min_index. Тогда получая наименьшую пару из seta (S, index) наши следующие индекс квеста next должен быть таким что c * S < v * d[next]. Так как наш xp после выполнения квеста next будет c * S + c * x[next]. Мы попадаем на новую сумму, причем выполнив при этом квест next смотрим попали ли мы в эту сумму с более выгодным (меньшим) для нас индекса до этого, если нет то обновляем минимум индекс для нашей полученной суммы. И инсертим пару (c * S + c * x[next], next) в наш set удалив при этом если был образец с худшим наименьшим индексом.

Мой кривой код который аксептится на icpc.kattis.com получился следующим

#include <iostream>
#include <vector>
#include <algorithm>
#include <bits/stdc++.h>
#include <iterator>
#include <set>

#define mp make_pair

using namespace std;

int main()
{
    set< pair <int, pair<int, int> > > arr;
    int n, v, c;
    cin >> n >> v >> c;
    int sumx = 0;

    for(int ct = 0; ct < n; ct++) {
        int x, d;
        cin >> x >> d;
        arr.insert(mp(v * d + c * x, mp(d, x + 5000 * ct)));
        sumx += x;
    }

    vector<int> difficulties;
    vector<int> xps;

    for(auto it = arr.begin(); it != arr.end(); it++) {
        int d = it->second.first;
        int x = it->second.second % 5000;
        difficulties.push_back(d);
        xps.push_back(x);
    }

    const int INF = 1000000000;
    vector<int> minimal_index (2000 * 2001, INF);
    set < pair<int,int> > q;
    int s1 = 0;
    int s2 = xps[0];
    minimal_index[s1] = 0;
    minimal_index[s2] = 0;
    q.insert (mp(s1, minimal_index[s1]));
    q.insert (mp(s2, minimal_index[s2]));
    int max_summ = 0;
    while (!q.empty()) {
        int summ = q.begin()->first;
        int index = q.begin()->second;
        q.erase (q.begin());
        max_summ = max(max_summ, summ);

        for (int j=index + 1; j < n; ++j) {
            int new_summ = summ + xps[j];
            if(summ * c < v * difficulties[j]) {
                int min_ind = minimal_index[new_summ];
                if (j < min_ind) {
                    q.erase (mp (new_summ, minimal_index[new_summ]));
                    minimal_index[new_summ] = j;
                    q.insert (mp (new_summ, j));
                }
            }
        }
    }
    cout << max_summ * (c - 1) + sumx;

}

Пост будет обновляться наверное. И добавлю еще решение других задач.