Задача геометрическая. Мы решим ее за n ^ 2 * log n время.

Назовем линию шириной t, полоской шириной t или просто полоской. Пусть у нас есть какое то решение и наша полоса не содержит на краю никакие точки. Тогда мы ее можем двигать до тех пор пока она станет содержать на краю у себя какую то точку. Теперь решение будет в форме что у нас есть какая то точка P, через нее мы провели полоску (так что P на краю полоски) и эта полоска содержит максимальное количество точек. Давайте выберем точку P, и заметим что полоску можно определять через угол и соответственно вращать на все 360 градусов и это будут различные полоски, давайте представлять такие полоски через угол.

Ключевое наблюдение в задаче, пусть есть другая точка Q. Вот пока мы вращаем нашу полоску начиная с какого то угла альфа она будет содержать точку Q. Потом пройдя какой то угол бетта она перестанет ее содержать. То есть существует отрезок [альфа, бетта] и если взять любой угол из этого отрезка и представить через нее полоску, то полоска будет содержать точку Q. То есть мы сведем задачу к задаче о максимальном пересечений отрезков, которая решается за n * log n.

Некоторые детали. Таких отрезков на самом деле два и они не пересекаются. Пусть альфа это угол соединяющий точки P и Q (считаем через арктангенс и получаем значение от -180 до 180). Поворот между бетта и альфа определяется через арксинус t / длина(PQ), нарисуйте на бумаге и поймите. Второй же отрезок будет таким. Альфа2 у второго отрезка будет центрально симметричен альфе1 первого, и чтобы получить бетта2 нужно поворачивать на тот же угол, только в обратную сторону.

Есть некоторые технические детали поиска максимального пересечения отрезков на окружности (то есть всех углов от -180 до 180). Они таковы. Пусть скажем у вас есть n отрезков, тогда у вас 2 * n концов. Упорядочите ваши углы запоминая каким отрезкам они принадлежали и были ли они началом или концом отрезка. Скажем получились упорядоченные значения -179, -150, 0, 50, 130, 170. Теперь считаете сколько отрезков содержать точку перед -179. То есть те чьи правые концы по кругу перешли так что теперь они в значений меньше своих левых концов. После этого идите поочередно через каждую точку от -179 до 170. Если вы перешли через точку представляющую левый конец значит вы вошли в новый отрезок (увеличиваете свой counter). Если же перешли правый конец уменьшаете counter.

Код который аксептиться на icpc.kattis.com я его почистил и за комментировал.

#include <iostream>
#include <vector>
#include <set>
#include <cmath>

#define mp make_pair
using namespace std;

long double eps = 1e-9;
long double SCALE = 180.0 / 3.141592653589793238463;

long double get_angle(long double x1, long double y1, long double x2, long double y2)
{
    return atan2l(x2 - x1, y2 - y1) * SCALE;
}

long double get_rotation(long double x1, long double y1, long double x2, long double y2, long double t)
{
    long double dx = x2 - x1;
    long double dy = y2 - y1;
    long double gipotenuza = sqrt(dx * dx + dy * dy);
    if(t >= gipotenuza)
        return 90;
    return asinl(t / gipotenuza) * SCALE;
}

long double symmetry(long double angle)
{
    if(angle <= 0)
        angle += 360;
    return angle - 180;
}

long double rotate_by_angle(long double angle, long double rot)
{
    angle += rot;
    if(angle > 180)
        angle -= 360;
    else if(angle <= -180)
        angle += 360;
    return angle;
}

int find_max_intersection(vector<pair<long double, long double> > &sl)
{
    set<pair<long double, int> > tochki;
    for(int i = 0; i < sl.size(); i++) {
        tochki.insert(mp(sl[i].first + eps, 2 * i)); /// left end of a segment
        tochki.insert(mp(sl[i].second - eps, 2 * i + 1)); /// right end of a segment
    }

    int ct = 0;
    /// compute the number of segments which contain -179.99... point
    /// (those which right end is less than left end)
    for(int i = 0; i < sl.size(); i++)
        if(sl[i].second < sl[i].first)
            ct += 1;
    int maxct = ct;

    for(auto iter = tochki.begin(); iter != tochki.end(); ++iter)
    {
        ct += -2 * (iter->second % 2) + 1; /// add counter 1 if entering segment, else deduct
        maxct = max(maxct, ct);
    }
    return maxct;
}

int main()
{
    int n, t, x, y;
    vector<int> xs;
    vector<int> ys;
    cin >> n >> t;
    for(int i = 0; i < n; i++)
    {
        cin >> x >> y;
        xs.push_back(x);
        ys.push_back(y);
    }

    int gl_max = 0;
    for(int i = 0; i < n; i++)
    {
        vector<pair<long double, long double> > sl;
        for(int j = 0; j < n; j++)
        {
            if(i == j)
                continue;
            /// define line via angle, so entering some angle it contains the point j
            /// then leaving another angle it stops containing the point j
            long double main_angle = get_angle(xs[i], ys[i], xs[j], ys[j]);
            long double rot = get_rotation(xs[i], ys[i], xs[j], ys[j], t);
            long double rev_main_angle = symmetry(main_angle);

            /// add two segments in which line contains the point j
            sl.push_back(mp(rotate_by_angle(main_angle, -rot), main_angle));
            sl.push_back(mp(rev_main_angle, rotate_by_angle(rev_main_angle, rot)));
        }
        /// now we need to compute maximum segment intersection
        int maxct = find_max_intersection(sl) + 1;
        gl_max = max(gl_max, maxct);
    }
    cout << gl_max;
}

Научимся считать за константу opportunity cost для каждого tuple (x, y, z).

Opportunity cost для (x, y, z) равен max по i=1...n величины max(x[i] - x, 0) + max(y[i] - y, 0) + max(z[i] - z, 0).

Покажем что не нужно пробегать все i, а только следующий индексы:

Пусть индексы m1, m2, m3, m4, m5, m6, m7 такие что

m1 максимизирует x[m]

m2 максимизирует y[m]

m3 максимизирует z[m]

m4 максимизирует x[m] + y[m]

m5 максимизирует y[m] + z[m]

m6 максимизирует x[m] + z[m]

m7 максимизирует x[m] + y[m] + z[m].

То есть например, y[m5] + z[m5] максимален среди y[i] + z[i] для любых i.

Докажем что максимум opportunity cost для произвольного (x, y, z) достигается на одном из m1, m2, m3, m4, m5, m6, m7. Пусть он достигся на i вот собственно он OC[i] = max(x[i] - x, 0) + max(y[i] - y, 0) + max(z[i] - z, 0), к примеру, пусть первый максимум при этом был нулем, второй и третий не нулевыми (остальные случаи аналогичны). Тогда OC[i] = 0 + (y[i] - y) + (z[i] - z) = y[i] + z[i] - y - z <= y[m5] + z[m5] - y - z = 0 + (y[m5] - y) + (z[m5] - z) <= max(x[m5] - x, 0) + max(y[m5] - y, 0) + max(z[m5] - z, 0) = OC[m5].

Последнее неравенство в силу a <= max(a, b) и b <= max(a, b). То есть получили что на m5 opportunity cost не меньше, а значит и максимизирующий i это m5.

То есть для каждого (x, y, z) если считаем за константу opporunity cost. Осталось посчитать для всех и найти наименьший.

Допустим что ваша последовательность выполнения квестов выглядит как то так, 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. Теперь понятно что если c * 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;

}

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