AtCoder Grand Contest 017 B - Moderate Differences

• 問題

B - Moderate Differences

• 解法

とするととなる。ここでに関して、またはが成立する。個のうち前者の個数が個だったとするとこのとき条件を満たすにはである必要がある。逆にこれが成立する時、条件を満たすように数列を作ることができる。であるかどうかの判定はでできるので全体としての時間計算量で答えを求められる。

#include <iostream>
using namespace std;

typedef long long int ll;

const ll mod = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 1e9;

int main()
{
	ll n,a,b,c,d;
	cin >> n >> a >> b >> c >> d;
	bool flag = false;
	for(int i = 0; i < n; i++){
		ll l = i*c-(n-1-i)*d, r = i*d-(n-1-i)*c;
		if(l<= b-a && b-a <= r) flag = true;
	}

	if(flag) cout << "YES" << endl;
	else cout << "NO" << endl;

	return 0;
}