Как мне дополнительно оптимизировать этот вопрос о сумме префиксов? ⇐ C++

[Anonymous]

У меня была такая проблема на соревновании по программированию:

Перед вами в очереди N человек, 1, 2, …, N. Вы знаете,
что человек на i-й позиции займет Ai единиц времени. Вы можете
подкупить человека перед вами на сумму Bi (это
его положение) и обменяться с ним позициями. Вы можете подкупить
несколько человек, но подкупить только того, кто перед вами. Поскольку
время — деньги, каждая единица времени в точности равна единице денег.
Предполагая, что подкуп человека и обмен с ним позициями происходит
мгновенно, вам нужно указать наименьшую сумму денег, которую вам нужно
потратить, чтобы оказаться впереди очереди.
Далее в очереди будут Q обновлений, и вам нужно будет сообщить ответ
для исходного дела и каждого дела после его создания. обновление.
Ввод: 1-я строка: N

2-я строка: N целых чисел, A1, A2, …, An.

3-я строка: N целых чисел, B1, B2, …, Bn.

4-я строка: Q

Следующие Q строк, где каждая строка представляет собой:
i, a и b
в каждом обновлении A = a и B = b.

Мой подход к решению этого вопроса заключался в вычислении префиксных сумм массива A
с начала и массива B с конца.
и затем для каждой позиции i я рассчитываю стоимость того, чтобы оказаться перед очередью, стоя там после подкупа всех до этой позиции. И берем минимум из всех.

Итак, для позиции i это будет A[i-1] + B.
Затем, после каждого обновления, я пересчитываю сумму префиксов для A и B из индекса i и снова нахожу минимум i.
И в худшем случае сложность будет: O(N * Q).
Это решение работало для запуска подзадач, но ограничение по времени было превосходит некоторые задачи последующих подзадач.

Есть ли способ дальнейшей оптимизации этого подхода или может ли существовать совершенно новый, лучший подход к этой проблеме?
Насколько я помню, это был мой код:
#include

using namespace std;

int main()
{
int N, Q, *A, *B;
cin >> N;

//Easier to calculate prefix sums
//A1 is stored at index 1, B2 is stored at index 1
//So A[1] + B[1] is A1 + B2
//So is A[0] + B[0] is 0 + B1 (Bribe everyone case)
//And so is A[N] + B[N] is AN + 0 (Bribe no one case)
A = new int[N + 1];
B = new int[N + 1];

A[0] = 0;
B[N] = 0;
for (int i = 0; i < N; i++)
{
cin >> A[i + 1];
}
for (int i = 0; i < N; i++)
{
cin >> A;
}

cin >> Q;

int ai = 1;
int bi = N - 1;
int a, b;
int iterator = 0;
int _min;

while (iterator a >> b;
bi = ai-1;
}
iterator++;
}

return 0;
}


Подробнее здесь: https://stackoverflow.com/questions/798 ... m-question