結果
問題 | No.1917 LCMST |
ユーザー | Georgi Petkov |
提出日時 | 2023-02-11 04:50:23 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,941 bytes |
コンパイル時間 | 1,904 ms |
コンパイル使用メモリ | 174,156 KB |
実行使用メモリ | 281,588 KB |
最終ジャッジ日時 | 2023-09-22 04:15:51 |
合計ジャッジ時間 | 41,963 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
5,728 KB |
testcase_01 | AC | 3 ms
5,964 KB |
testcase_02 | AC | 4 ms
5,752 KB |
testcase_03 | AC | 11 ms
6,180 KB |
testcase_04 | AC | 11 ms
5,984 KB |
testcase_05 | AC | 12 ms
6,048 KB |
testcase_06 | AC | 11 ms
5,992 KB |
testcase_07 | AC | 12 ms
5,968 KB |
testcase_08 | AC | 4 ms
5,660 KB |
testcase_09 | AC | 3,377 ms
145,968 KB |
testcase_10 | AC | 3,364 ms
145,236 KB |
testcase_11 | AC | 3,275 ms
145,088 KB |
testcase_12 | AC | 2,346 ms
80,168 KB |
testcase_13 | AC | 529 ms
17,968 KB |
testcase_14 | AC | 2,755 ms
79,884 KB |
testcase_15 | AC | 276 ms
10,200 KB |
testcase_16 | AC | 551 ms
18,696 KB |
testcase_17 | AC | 995 ms
28,108 KB |
testcase_18 | AC | 1,338 ms
45,580 KB |
testcase_19 | AC | 259 ms
9,544 KB |
testcase_20 | AC | 175 ms
7,760 KB |
testcase_21 | AC | 283 ms
11,696 KB |
testcase_22 | AC | 175 ms
7,812 KB |
testcase_23 | AC | 173 ms
7,736 KB |
testcase_24 | AC | 265 ms
9,528 KB |
testcase_25 | AC | 180 ms
7,976 KB |
testcase_26 | AC | 203 ms
8,092 KB |
testcase_27 | AC | 221 ms
9,196 KB |
testcase_28 | AC | 239 ms
9,392 KB |
testcase_29 | AC | 2,000 ms
276,492 KB |
testcase_30 | AC | 2,001 ms
277,904 KB |
testcase_31 | AC | 1,954 ms
276,924 KB |
testcase_32 | AC | 1,978 ms
276,424 KB |
testcase_33 | AC | 1,965 ms
276,680 KB |
testcase_34 | AC | 83 ms
5,676 KB |
testcase_35 | AC | 82 ms
5,800 KB |
testcase_36 | AC | 83 ms
5,896 KB |
testcase_37 | TLE | - |
testcase_38 | -- | - |
testcase_39 | -- | - |
testcase_40 | -- | - |
testcase_41 | -- | - |
testcase_42 | -- | - |
testcase_43 | -- | - |
testcase_44 | -- | - |
ソースコード
#include <bits/stdc++.h> #define endl '\n' using namespace std; const int maxn = 1e5 + 3; const long long inf = 1e18; const int bucket = 500; int n; bool is[maxn]; long long ans; vector <int> not_taken[maxn]; int taken[maxn]; vector <int> get_divisors(int x) { vector <int> ans; for (int i = 1; i * i <= x; i++) if (x % i == 0) { ans.push_back(i); if (i * i != x) ans.push_back(x / i); } return ans; } void add_num(int x) { for (auto i: get_divisors(x)) not_taken[i].push_back(x); } void read() { cin >> n; for (int i = 1; i <= n; i++) { int x; cin >> x; if (is[x]) { ans += x; continue; } is[x] = true; } } struct edge { int from, to; long long w; edge(int _from, int _to, long long _w) {from = _from, to = _to, w = _w;} bool operator < (const edge &other) const { return w > other.w; } }; ostream &operator << (ostream &out, const edge &e) { out << "edge from " << e.from << " to " << e.to << " with weight " << e.w << endl; return out; } void add_edges(int x, priority_queue <edge> &pq) { for (auto i: get_divisors(x)) { if (i > bucket) { for (auto j: not_taken[i]) if (is[j]) pq.push(edge(x, j, (long long)x * j / i)); } else { if (!taken[i] || x < taken[i]) taken[i] = x; } } } edge get_best_edge(priority_queue <edge> &pq) { while (!pq.empty()) { auto e = pq.top(); if (!is[e.to]) { pq.pop(); continue; } return e; } return edge(-1, -1, inf); } edge get_single(int idx) { while (!not_taken[idx].empty() && !is[not_taken[idx].back()]) not_taken[idx].pop_back(); if (not_taken[idx].empty() || !taken[idx]) return edge(-1, -1, inf); int a = taken[idx], b = not_taken[idx].back(); return edge(a, b, (long long)a * b / idx); } edge get_multiple() { edge ans = {-1, -1, inf}; for (int i = 1; i <= bucket; i++) ans = max(ans, get_single(i)); return ans; } void solve() { int left = 0; for (int i = maxn-1; i >= 1; i--) if (is[i]) add_num(i), left++; for (int i = 1; i < maxn; i++) if (is[i]) { is[i] = false; priority_queue <edge> pq; add_edges(i, pq); left--; while (left) { auto e = get_best_edge(pq); e = max(e, get_multiple()); ans += e.w; is[e.to] = is[e.from] = false; add_edges(e.to, pq); left--; } break; } cout << ans << endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); read(); solve(); }