結果

問題 No.719 Coprime
ユーザー Pachicobue
提出日時 2018-07-28 01:32:46
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,684 bytes
コンパイル時間 1,787 ms
コンパイル使用メモリ 198,728 KB
最終ジャッジ日時 2025-01-06 12:08:26
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 43 WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

//=================================
// Created on: 2018/07/28 01:03:56
//=================================
#include <bits/stdc++.h>
#define show(x) std::cerr << #x << " = " << x << std::endl
int main()
{
    constexpr int NUM = 11;
    constexpr int MAX = 1 << NUM;
    constexpr int p[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
    int N;
    std::cin >> N;
    std::vector<int> mask(N + 1, 0), maxp(N + 1, 0);
    for (int i = 2, cnt = 0; i <= N; i++) {
        if (maxp[i] != 0) { continue; }
        if (cnt < NUM) { mask[i] |= (1 << cnt); }
        for (int j = 2; i * j <= N; j++) { mask[i * j] |= (1 << cnt), maxp[i * j] = i; }
        cnt++;
    }
    std::vector<int> large(MAX, 0);
    for (int ps = 0; ps < NUM; ps++) {
        std::vector<bool> used(N + 1, false);
        for (int i = N; i >= 2; i--) {
            if (maxp[i] <= 31 or used[maxp[i]]) { continue; }
            bool ok = true;
            for (int j = 0; j < NUM; j++) {
                if (((ps & (1 << j)) > 0) and i % p[j] == 0) {
                    ok = false;
                    break;
                }
            }
            if (ok) { large[ps] += i, used[maxp[i]] = true; }
        }
    }
    constexpr int INF = 1 << 30;
    std::vector<int> dp(MAX, -INF);
    dp[0] = 0;
    for (int i = 2; i <= N; i++) {
        if (maxp[i] > 31) { continue; }
        for (int j = MAX - 1; j >= 0; j--) {
            if (dp[j] == -INF or (j & mask[i]) > 0) { continue; }
            dp[j | mask[i]] = std::max(dp[j | mask[i]], dp[j] + i);
        }
    }
    int ans = 0;
    for (int i = 0; i < MAX; i++) { ans = std::max(ans, dp[i] + large[i]); }
    std::cout << ans << std::endl;
    return 0;
}
0