結果

問題 No.3502 GCD Knapsack
コンテスト
ユーザー Azaki
提出日時 2026-04-18 04:20:39
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
TLE  
実行時間 -
コード長 1,440 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,904 ms
コンパイル使用メモリ 178,248 KB
実行使用メモリ 45,340 KB
最終ジャッジ日時 2026-04-18 04:21:25
合計ジャッジ時間 14,457 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 34
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

/**
 * Tối ưu hóa:
 * 1. Dùng unordered_map để truy cập O(1).
 * 2. Nhóm các vật phẩm có cùng w_i để giảm số lần tính ước.
 * 3. Tính toán trực tiếp trong lúc tìm ước.
 */

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    long long W;
    if (!(cin >> N >> W)) return 0;

    unordered_map<int, long long> weights;
    for (int i = 0; i < N; ++i) {
        int w, v;
        cin >> w >> v;
        if (w >= W) {
            weights[w] += v;
        }
    }

    // gcd_sums lưu: [giá trị GCD g] -> [tổng giá trị v thu được]
    unordered_map<int, long long> gcd_sums;
    gcd_sums.reserve(100000); // Giảm việc rehash

    for (auto const& [w, v] : weights) {
        // Tìm ước của w trong O(sqrt(w))
        for (int d = 1; d * d <= w; ++d) {
            if (w % d == 0) {
                if (d >= W) {
                    gcd_sums[d] += v;
                }
                int other = w / d;
                if (other != d && other >= W) {
                    gcd_sums[other] += v;
                }
            }
        }
    }

    long long max_ans = 0;
    for (auto const& [g, total_v] : gcd_sums) {
        if (total_v > max_ans) {
            max_ans = total_v;
        }
    }

    cout << max_ans << endl;

    return 0;
}
0