結果
問題 | No.1917 LCMST |
ユーザー | kwm_t |
提出日時 | 2022-04-30 14:50:48 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 356 ms / 4,000 ms |
コード長 | 1,756 bytes |
コンパイル時間 | 5,622 ms |
コンパイル使用メモリ | 272,244 KB |
実行使用メモリ | 47,508 KB |
最終ジャッジ日時 | 2023-09-12 07:26:44 |
合計ジャッジ時間 | 17,553 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 2 ms
4,380 KB |
testcase_02 | AC | 3 ms
4,376 KB |
testcase_03 | AC | 5 ms
4,380 KB |
testcase_04 | AC | 5 ms
4,384 KB |
testcase_05 | AC | 5 ms
4,384 KB |
testcase_06 | AC | 5 ms
4,376 KB |
testcase_07 | AC | 5 ms
4,380 KB |
testcase_08 | AC | 3 ms
4,380 KB |
testcase_09 | AC | 333 ms
31,044 KB |
testcase_10 | AC | 332 ms
29,632 KB |
testcase_11 | AC | 330 ms
29,684 KB |
testcase_12 | AC | 304 ms
29,572 KB |
testcase_13 | AC | 216 ms
20,368 KB |
testcase_14 | AC | 314 ms
29,680 KB |
testcase_15 | AC | 193 ms
16,456 KB |
testcase_16 | AC | 220 ms
21,188 KB |
testcase_17 | AC | 244 ms
30,464 KB |
testcase_18 | AC | 268 ms
28,960 KB |
testcase_19 | AC | 195 ms
17,064 KB |
testcase_20 | AC | 178 ms
13,404 KB |
testcase_21 | AC | 196 ms
16,152 KB |
testcase_22 | AC | 180 ms
13,396 KB |
testcase_23 | AC | 180 ms
13,492 KB |
testcase_24 | AC | 195 ms
16,936 KB |
testcase_25 | AC | 181 ms
13,536 KB |
testcase_26 | AC | 185 ms
13,664 KB |
testcase_27 | AC | 188 ms
15,976 KB |
testcase_28 | AC | 192 ms
17,680 KB |
testcase_29 | AC | 353 ms
46,284 KB |
testcase_30 | AC | 356 ms
46,536 KB |
testcase_31 | AC | 355 ms
47,508 KB |
testcase_32 | AC | 355 ms
47,024 KB |
testcase_33 | AC | 356 ms
47,312 KB |
testcase_34 | AC | 110 ms
11,364 KB |
testcase_35 | AC | 110 ms
11,448 KB |
testcase_36 | AC | 111 ms
11,384 KB |
testcase_37 | AC | 355 ms
46,216 KB |
testcase_38 | AC | 353 ms
46,548 KB |
testcase_39 | AC | 354 ms
45,856 KB |
testcase_40 | AC | 352 ms
46,076 KB |
testcase_41 | AC | 352 ms
47,508 KB |
testcase_42 | AC | 350 ms
46,716 KB |
testcase_43 | AC | 111 ms
11,620 KB |
testcase_44 | AC | 112 ms
11,600 KB |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; //using mint = modint1000000007; //const int mod = 1000000007; //using mint = modint998244353; //const int mod = 998244353; //const int INF = 1e9; //const long long LINF = 1e18; #define rep(i, n) for (int i = 0; i < (n); ++i) #define rep2(i,l,r)for(int i=(l);i<(r);++i) #define rrep(i, n) for (int i = (n-1); i >= 0; --i) #define rrep2(i,l,r)for(int i=(r-1);i>=(l);--i) #define all(x) (x).begin(),(x).end() #define allR(x) (x).rbegin(),(x).rend() #define endl "\n" #define P pair<int,int> template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; } template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<long long>a(n); long long ans = 0; rep(i, n) { cin >> a[i]; ans += a[i]; } sort(all(a)); a.erase(unique(all(a)), a.end()); vector<int>memo(100005, -1); rep(i, a.size()) { ans -= a[i]; memo[a[i]] = i; } vector<pair<long long, P>>edge; rep2(i, 1, a.back() + 1) { vector<pair<long long,int>>v; for (int j = i; j <= 100000; j += i) { if (-1 != memo[j])v.push_back({ j,memo[j] }); } if (v.size() <= 1)continue; rep2(j, 1, v.size()) { long long dist = v[0].first * v[j].first / (long long)i; edge.push_back({ dist,{v[0].second,v[j].second} }); } } dsu uf(a.size()); sort(all(edge)); rep(i, edge.size()) { long long d = edge[i].first; int x = edge[i].second.first; int y = edge[i].second.second; if (uf.same(x, y)) continue; uf.merge(x, y); ans += d; } cout << ans << endl; return 0; }