結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 7 ms
8,700 KB
testcase_01 AC 7 ms
8,244 KB
testcase_02 AC 7 ms
8,264 KB
testcase_03 AC 7 ms
8,200 KB
testcase_04 AC 8 ms
8,180 KB
testcase_05 AC 7 ms
8,308 KB
testcase_06 AC 7 ms
8,780 KB
testcase_07 AC 7 ms
8,172 KB
testcase_08 AC 7 ms
8,224 KB
testcase_09 AC 8 ms
8,348 KB
testcase_10 AC 7 ms
8,208 KB
testcase_11 AC 8 ms
8,532 KB
testcase_12 AC 8 ms
8,312 KB
testcase_13 AC 8 ms
8,076 KB
testcase_14 AC 194 ms
13,900 KB
testcase_15 AC 154 ms
13,268 KB
testcase_16 AC 168 ms
13,204 KB
testcase_17 AC 135 ms
12,796 KB
testcase_18 AC 175 ms
13,492 KB
testcase_19 AC 150 ms
12,940 KB
testcase_20 AC 193 ms
13,652 KB
testcase_21 AC 181 ms
13,648 KB
testcase_22 AC 183 ms
13,552 KB
testcase_23 AC 124 ms
12,440 KB
testcase_24 AC 244 ms
17,152 KB
testcase_25 AC 240 ms
17,192 KB
testcase_26 AC 240 ms
17,060 KB
testcase_27 AC 240 ms
17,192 KB
testcase_28 AC 243 ms
17,068 KB
testcase_29 AC 241 ms
17,068 KB
testcase_30 AC 243 ms
17,060 KB
testcase_31 AC 240 ms
17,192 KB
testcase_32 AC 244 ms
17,064 KB
testcase_33 AC 240 ms
17,064 KB
testcase_34 AC 8 ms
8,080 KB
testcase_35 AC 7 ms
8,192 KB
testcase_36 AC 59 ms
9,144 KB
testcase_37 AC 7 ms
8,312 KB
testcase_38 AC 60 ms
9,144 KB
testcase_39 AC 7 ms
8,216 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