結果

問題 No.3502 GCD Knapsack
コンテスト
ユーザー Azaki
提出日時 2026-04-18 04:19:24
言語 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  
実行時間 -
コード長 2,110 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,947 ms
コンパイル使用メモリ 184,876 KB
実行使用メモリ 31,464 KB
最終ジャッジ日時 2026-04-18 04:19:56
合計ジャッジ時間 9,391 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 34
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

/**
 * Thuật toán tối ưu cho w_i lớn:
 * 1. Gộp các v_i có cùng w_i.
 * 2. Tìm tất cả các ước d >= W của TẤT CẢ các w_i.
 * 3. Với mỗi d, tính tổng v_i của các w_i là bội của d.
 */

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

    int N;
    long long W;
    cin >> N >> W;

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

    if (weight_to_v.empty()) {
        cout << 0 << endl;
        return 0;
    }

    // Lấy danh sách các trọng lượng duy nhất >= W
    vector<int> unique_ws;
    for (auto const& [w, v] : weight_to_v) {
        unique_ws.push_back(w);
    }

    // Tìm tập hợp tất cả các ước d >= W khả thi
    vector<int> candidates;
    for (int w : unique_ws) {
        for (int d = 1; d * d <= w; ++d) {
            if (w % d == 0) {
                if (d >= W) candidates.push_back(d);
                if (w / d >= W) candidates.push_back(w / d);
            }
        }
    }
    
    // Sắp xếp và loại bỏ trùng lặp để giảm số lượng g cần kiểm tra
    sort(candidates.begin(), candidates.end());
    candidates.erase(unique(candidates.begin(), candidates.end()), candidates.end());

    long long max_val = 0;

    // Với mỗi ứng viên g, tính tổng giá trị các vật phẩm có trọng lượng chia hết cho g
    for (int g : candidates) {
        long long current_v = 0;
        // Chỉ duyệt các w trong unique_ws là bội của g
        // Tối ưu: bắt đầu tìm từ vị trí đầu tiên >= g
        auto it = lower_bound(unique_ws.begin(), unique_ws.end(), g);
        for (; it != unique_ws.end(); ++it) {
            if (*it % g == 0) {
                current_v += weight_to_v[*it];
            }
        }
        max_val = max(max_val, current_v);
    }

    cout << max_val << endl;

    return 0;
}
0