結果

問題 No.2718 Best Consonance
ユーザー luanmengleiluanmenglei
提出日時 2024-04-05 22:14:03
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 228 ms / 4,000 ms
コード長 2,122 bytes
コンパイル時間 2,322 ms
コンパイル使用メモリ 212,688 KB
実行使用メモリ 17,196 KB
最終ジャッジ日時 2024-10-02 12:46:12
合計ジャッジ時間 7,889 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 7 ms
8,188 KB
testcase_01 AC 6 ms
7,992 KB
testcase_02 AC 8 ms
8,212 KB
testcase_03 AC 7 ms
8,116 KB
testcase_04 AC 6 ms
8,436 KB
testcase_05 AC 7 ms
8,156 KB
testcase_06 AC 6 ms
8,140 KB
testcase_07 AC 6 ms
8,032 KB
testcase_08 AC 6 ms
8,028 KB
testcase_09 AC 7 ms
8,092 KB
testcase_10 AC 7 ms
8,064 KB
testcase_11 AC 7 ms
8,084 KB
testcase_12 AC 8 ms
8,112 KB
testcase_13 AC 8 ms
8,152 KB
testcase_14 AC 167 ms
13,652 KB
testcase_15 AC 148 ms
13,016 KB
testcase_16 AC 146 ms
13,340 KB
testcase_17 AC 123 ms
12,676 KB
testcase_18 AC 160 ms
13,368 KB
testcase_19 AC 137 ms
12,944 KB
testcase_20 AC 172 ms
13,656 KB
testcase_21 AC 174 ms
13,524 KB
testcase_22 AC 173 ms
13,552 KB
testcase_23 AC 116 ms
12,440 KB
testcase_24 AC 228 ms
17,196 KB
testcase_25 AC 221 ms
17,064 KB
testcase_26 AC 218 ms
17,068 KB
testcase_27 AC 222 ms
17,068 KB
testcase_28 AC 223 ms
17,196 KB
testcase_29 AC 220 ms
17,072 KB
testcase_30 AC 223 ms
17,196 KB
testcase_31 AC 221 ms
17,064 KB
testcase_32 AC 222 ms
17,196 KB
testcase_33 AC 217 ms
17,192 KB
testcase_34 AC 6 ms
8,208 KB
testcase_35 AC 7 ms
8,284 KB
testcase_36 AC 53 ms
9,148 KB
testcase_37 AC 7 ms
8,364 KB
testcase_38 AC 53 ms
9,012 KB
testcase_39 AC 7 ms
8,116 KB
権限があれば一括ダウンロードができます

ソースコード

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