Обл 24-25 1 день А

Информатика
1 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define F first
#define S second
const int INF = 1e18;
const int N = 1e7+7;


signed main() {
	int n, h, x, y;
	cin >> n >> h >> x >> y;
	vector <int> a(N);
	int mx = 0;
	int mn = INF;
	for ( int i =1 ;i <= n; i++ ) {
		cin >> a[i];
		mx = max(a[i], mx);
		mn = min(a[i], mn);
	}
	if ( x == y ) {
		if ( h >= mx ) {
			cout << 0;
			return 0;
		} else {
			cout <<  (mx - h) * x;
		}
	} else if ( mx == mn ) {
		if ( h >= mx ) {
			cout << 0;
			return 0;
		}
		int q = (mx - h) * x;
		int k = (mx-h) * y * n;
		cout << min(q, k);
		return 0;
	}

	return 0;
}

Можете помочь с решением данной задача на фулл?

image
image894×834 142 KB

2

откуда можно посмотреть 2 тур

3

2 тур которого еще не было?)) ниоткуда.

4

Заметим что если мы сделали K действий первого типа, то их выгодно сделать как можно раньше, то есть в самом начале.

Допустим мы знаем число K, как тогда посчитать ответ?

Ну очевидно это будет значение K \cdot x + y \cdot \sum\limits_{i=1}^{n} \max(0, a[i] - (h + K)), так как для того чтобы перепрыгнуть забор превышающий высоту нашего прыжка нам нужно применить действие второго типа.

Допустим мы посчитали ответ для K = 0, теперь чтобы посчитать его для K = 1, это достаточно просто, можешь сделать это сам расписав разницу формулы выше. Так ты сможешь переходить к следующему K + 1 для любого K за O(1) или за O(\log(n)). Ну и уже тут это получает 100 баллов, но можно подумать дальше:

  1. Что делать если ограничение на высоты будет 10^9?

  2. Нужно ли считать ответ для каждого K? Можно ли найти оптимальное K быстрее?

5 лайков