29pubgstate29

Ну просто проверяйте в operator*: если nullptr, то бросайте исключение.

В вашем решении есть ошибки: Вы считаете сумму двух чисел от 0 до N, а не от 1 до N.

А главная проблема вашего решения в том, что оно "жадное". Вы жадно берете первую папавшуюся пару, как будто так будет оптимально. Но это не так. Например, если у вас остались гири весами 2, 3, 4, 5, то брать пару 2+3 = 5 нельзя, ведь тогда оставшиеся 4+5=9 дадут не простое число.

Это действительно можно решать через задачу о паросочетании как сказал Alexandroppolus. Вот только все алгоритмы работают за O(N^3), так что для N=500000 это решение будет работь очень долго.

Но в вашем случае граф очень специфичный, так что надо придумать какой-то шаблон. Например, можно взять максимальное простое число P <= N+1 и набирать его всеми возможными парами (1+(P-1), 2+(P-2)). В итоге у вас остнется одна нечетная гиря (P+1)/2 и все гири >=P. Например, если N+1 простое - то это оптимальный способ.

Я бы посоветовал написать решение через максимальное паросочетание и прогнать его для всех N <=200. Получите оптимальные ответы, посмотрите на них. Поищите какой-то паттерн в количестве пар, потом попробуйте придумать способ такое количество набрать.

И еще немного покритикую ваш код.
f==true. Зачем? Можно написать if(f). А вообще вам тут f не нужно, пишите if(Check(i+j)).

Вместо

if(a[j]!=0&&a[i]!=0&&i!=j) { 
  ...
}

стоит использовать "ранний выход":

if(!a[i] || !a[j] || i == j) continue; 
...

Так вложенность и сложность кода меньше. Его проще читать и понимать.

Вместо прверки, что i != j, можно внутренний цикл гнать от n до i+1. Вам же не надо перебирать отдельно пары 1+10 и 10+1? Всегда считайте, что первое число меньше второго в паре.

Ну, и отступы, ради всего святого, расставьте аккуратно. Любой редактор кода умеет их делать автоматически.

Edit:
Совместо с Alexandroppolus в комментариях придумали следующее решение: Берете минимальное простое число, большее N. Обзовем его P. Тогда берем пары N+(P-N), (N-1)+(P-N+1)... и т.д. В этих парах одно число четное, другое нечетное. И всего они покроют отрезок четной длины без дырок. Потом задача сводится к такой же, только уже с максимальным числом не N, а P-N-1.
Эта жадность работает, потому что она всегда соберет максимально теоретически возможное количетсво пар. Может только одна 1 в конце останется.

Если вы хотите оптимизировать программу по времени выполнения, то необходимо задать нужный размер матрицы с самого начала, так как он у вас известен. Например так:

std::size_t r = 0, c = 0;
std::cin >> r >> c;
std::vector<std::vector<int>> matrix(r, std::vector<int>(c));

Далее, у вас же просто числа, которые можно читать сразу в переменную:

for (std::size_t i = 0; i < c; ++i)
	for (std::size_t j = 0; j < r; ++ j)
		cin >> matrix[j][i];

Сразу скажу, я это не компилировал, не запускал и не проверял работает или нет. Если возникают какие-то ошибки, то пользуйтесь отладчиком.

PS
Первая ошибка в вашем коде заключается в том, что вектор g пустой в момент обращения по индексу. Замените [] на метод at() и получите исключение.