結果

問題 No.3504 Insert Maze
コンテスト
ユーザー Azaki
提出日時 2026-04-18 04:33:32
言語 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
結果
WA  
実行時間 -
コード長 2,425 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,806 ms
コンパイル使用メモリ 165,132 KB
実行使用メモリ 7,976 KB
最終ジャッジ日時 2026-04-18 04:33:44
合計ジャッジ時間 7,442 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 85
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

using namespace std;

/**
 * Bài toán: No.3478 GCD Knapsack
 * Giải thuật: 
 * Với mỗi g >= W, ta lấy tất cả các vật phẩm có trọng lượng là bội của g.
 * GCD của tập hợp này chắc chắn là một bội của g, do đó GCD >= g >= W.
 */

// Đặt mảng tĩnh ở ngoài để tránh lỗi Runtime Error (Stack Overflow)
// Kích thước 200005 để bao phủ giới hạn 2e5 của đề bài
long long sum_v[200005];

int main() {
    // Tối ưu hóa nhập xuất là bắt buộc trên yukicoder
    ios::sync_with_stdio(false);
    cin.tie(NULL);

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

    int max_x = 0;
    for (int i = 0; i < N; i++) {
        int x;
        long long y;
        cin >> x >> y;
        // Bảo vệ mảng để tránh RE
        if (x >= 0 && x <= 200000) {
            sum_v[x] += y;
            if (x > max_x) max_x = x;
        }
    }

    // Nếu W vượt quá mọi trọng lượng đang có, không thể chọn được GCD >= W
    if (W > 200000 || W > max_x) {
        // Đề bài: "Nếu có thể... Nếu không..." 
        // Trong yukicoder bài này, nếu không chọn được thì không in gì 
        // hoặc đề bài yêu cầu cụ thể. Dựa trên mô tả, ta kiểm tra ans.
    }

    long long ans = -1;

    // Duyệt g là GCD tiềm năng, g phải >= W
    for (int g = (int)W; g <= max_x; g++) {
        // Nếu g = 0 thì bỏ qua (tránh lỗi chia cho 0 mặc dù W >= 1)
        if (g == 0) continue;

        long long current_v = 0;
        bool found = false;

        // Tính tổng giá trị của tất cả vật phẩm có trọng lượng là bội số của g
        for (int m = g; m <= max_x; m += g) {
            if (sum_v[m] > 0) {
                current_v += sum_v[m];
                found = true;
            }
        }

        if (found) {
            if (ans == -1 || current_v > ans) {
                ans = current_v;
            }
        }
    }

    // Nếu ans vẫn là -1 nghĩa là không có vật phẩm nào có X_i >= W
    if (ans == -1) {
        // Một số bài yêu cầu in 0 hoặc -1, nhưng thường là không có kết quả hợp lệ
        // Hãy thử in kết quả nếu tìm thấy
    } else {
        cout << ans << endl;
    }

    return 0;
}
0