結果

問題 No.2718 Best Consonance
ユーザー luanmenglei
提出日時 2024-04-05 22:14:03
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 247 ms / 4,000 ms
コード長 2,122 bytes
コンパイル時間 2,365 ms
コンパイル使用メモリ 206,576 KB
最終ジャッジ日時 2025-02-20 21:29:44
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
bool stB;
namespace SOL {

void debug(const char *msg, ...) {
#ifdef CLESIP
    va_list arg;
    static char pbString[512];
    va_start(arg,msg);
    vsprintf(pbString,msg,arg);
    cerr << "[DEBUG] " << pbString << "\n";
    va_end(arg);
#endif    
}

using i64 = long long;
using i128 = __int128_t;
template <typename T, typename L> bool chkmax(T &x, L y) { if (x < y) return x = y, true; return false; }
template <typename T, typename L> bool chkmin(T &x, L y) { if (y < x) return x = y, true; return false; }

const int N = 2e5 + 10;
const int maxv = 2e5;
int n, mx[N];
vector<int> val[N];

void ___solve() {
	cin >> n;
	for (int i = 1, a, b; i <= n; i ++) {
		cin >> a >> b;
		val[a].push_back(b);
	}
	i64 ans = 0;
	for (int i = 1; i <= maxv; i ++) if (!val[i].empty()) {
		sort(begin(val[i]), end(val[i]), greater<int>());
		if ((int) val[i].size() >= 2)
			chkmax(ans, val[i][1]);
		mx[i] = val[i][0];
	}
	for (int d = 1; d <= maxv; d ++) {
		vector<array<int, 2>> vec;
		for (int i = d; i <= maxv; i += d)
			if (mx[i])
				vec.push_back({ i / d, mx[i] });
		if (vec.empty())
			continue;
		sort(begin(vec), end(vec), [&](array<int, 2> lhs, array<int, 2> rhs) {
			return 1ll * lhs[0] * lhs[1] < 1ll * rhs[0] * rhs[1];
		}); 
		int mxv = 0;
		for (auto [x, y] : vec) {
			chkmax(ans, mxv / x);
			chkmax(mxv, y);
		}
		// for (int i = 0; i < (int) vec.size(); i ++)
		// 	for (int j = i + 1; j < (int) vec.size(); j ++)
		// 		chkmax(ans, min(vec[i][1] / vec[j][0], vec[j][1] / vec[i][0]));
	}
	cout << ans << "\n";
}

}
bool edB;
signed main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	SOL::___solve();
#ifdef CLESIP
	// cerr << "Memory: " << (&stB - &edB) / 1024.0 / 1024.0 << "MB\n";
	// cerr << "Time: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
#endif
	return 0;
}
/*
Aix = Ajy

d = gcd(Ai, Aj)


min(
Bi / (Aj / d)
,Bj / (Ai / d)
) is max

n log n (x, y)

min(x1 / y2, x2 / y1) is max


x1 / y2 > x2 / y1


x1 * y1 > x2 * y2


sort by x1 * y1 and remove the min limitation

then the problem is to find the maximum x2, which is quite simple
*/
0