Задача на максимальное значение

Информатика
1

как решить эту задачу? (прошло только на 15б, дальше идеи нет)

Screenshot 2023-02-02 180046
Screenshot 2023-02-02 1800461118×820 57.6 KB

1 лайк
2

Обрати внимание на ограничение элементов массива. Можно ссылку на задачу?

2 лайка
3
Подзадача 2

Обратим внимание на то, что a[i] <= 2000. Благодаря такому ограничению, мы сможем проверить все пары [a[i], a[j]], где 1 <= a[i], a[j] <= 2000. Асимптотика подобного решения будет: O(n^2)

Код 
for (int i = 1; i <= n; i++){
			for (int j = i + 1; j <= n; j++)
				ans = max(ans, 1LL * (a[i] + a[j]) * (j - i));
Подзадача 3

В этой подзадаче массив a отсортирован по возрастанию. На n- той позиции стоит максимальный a[i], значит, мы можем провести операцию со всеми элементы от 1 до n - 1.

Код 
for (int i = 1; i <= n; ++i)		    
       ans = max(ans, 1LL * (a[i] + a[n]) * (n - i));
Подзадача 4

Небольшой факт под номером 1:

Ответ на задачу будет лежать на Возрастающей Подпоследовательности (далее ВП). (Очевидный факт, оставляю вам это в качестве доказательства :slight_smile:)

Создадим vector<pair<int, int>> v. В этом векторе мы будем хранить нашу ВП(само число и его индекс в массиве). Проходимся по всем элементам массива и проверяем, если a[i] будет больше, чем последний элемент нашей ВП, то мы добавим пару [a[i], i] в вектор.

Небольшой факт под номером 2:

Если со всеми элементами ВП провести операцию с a[i] и представить ответы ввиде функции, то функция будет изначально возрастать, после убывать(свойство унимодальной функции). (Тривиальный факт, доказательство уходит читающим в качестве ДЗ.)

Из факта номер 2 можно узнать, что функция является унимодальной, это означает, что с помощью Тернарного(Троичный, Ернарный) Поиска, мы сможем найти точку максимума функции.

Код 
ll calc(int i, int j) {
	return (1LL * (a[j] + v[i].first) * (j - v[i].second));
}

v.push_back({0, 0});
for (int i = 1; i <= n; ++i) {
	if (v.back().first < a[i])
		v.pb({a[i], i});
	int l = 1, r = v.size() - 1;
	for (int j = 1; j <= 100; ++j) {
		int m1 = l + (r - l) / 3;
		int m2 = r - (r - l) / 3;
		ll val1 = calc(m1, i);
		ll val2 = calc(m2, i);
		ans = max(ans, val1);
		ans = max(ans, val2);
		if (val1 < val2)
			l = m1;
		else
			r = m2;
	}
}

P.S. Не смог нормально расписать доказательство фактов, так что пока так :frowning:

3 лайка
4

Можно ссылку на задачу?

1 лайк
5

Кажется эта задача из какой-то закрытой группы, по крайней мере я не видел ее где-то в тренировках/архиве, а только в закрытой группе.

6

вторая подзадача не проходит :smiling_face_with_tear:

1 лайк
7

Что именно ты перебираешь?

8

все возможные пары ij и это вроде работает за n^2 10^12 и это тл, но не знаю как фиксировать

2 лайка
9

Он имел ввиду перебирать значения элементов и брать самый правый/самый левый из них для максимизации j - i

А так как различных значений элементов всего 2000, то это будет работать за 2000^2

10

Упс, сори, вместо [a[i], a[j]] написал просто их индексы [i, j]. Уже исправил :slight_smile:

UPD: лол, код из подзадачи n <= 2000 взял, сори :frowning:

11

Могу скинуть код на 100 баллов(Полное решение)

2 лайка