提出 #69511973

---

ソースコード 拡げる

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

using namespace std;

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

    int n, m;
    cin >> n >> m;

    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());

    // Group songs by their B_j requirement and sort by C_j descending
    vector<vector<long long>> songs_by_b(n + 1);
    for (int i = 0; i < m; ++i) {
        int b;
        long long c;
        cin >> b >> c;
        if (b <= n) {
            songs_by_b[b].push_back(c);
        }
    }

    for (int b = 0; b <= n; ++b) {
        sort(songs_by_b[b].rbegin(), songs_by_b[b].rend());
    }

    // Precompute R(p) values
    vector<long long> r(m + 1, 0);
    for (int p = 1; p <= m; ++p) {
        long long sum_a_lt_p = 0;
        long long count_a_ge_p = 0;
        for (int val : a) {
            if (val >= p) {
                count_a_ge_p++;
            } else {
                sum_a_lt_p += val;
            }
        }
        r[p] = (long long)p * count_a_ge_p + sum_a_lt_p;
    }

    // dp[p] is a map from sum_of_b to max_excitement
    vector<map<int, long long>> dp(m + 1);
    dp[0][0] = 0; // Base case: 0 songs, 0 requirement sum, 0 excitement

    // Iterate B values from high to low
    for (int b = n; b >= 0; --b) {
        if (songs_by_b[b].empty()) {
            continue;
        }

        vector<map<int, long long>> next_dp = dp;
        long long current_c_sum = 0;

        // Consider taking k songs of requirement b
        for (int k = 1; k <= songs_by_b[b].size(); ++k) {
            current_c_sum += songs_by_b[b][k - 1];
            
            // Combine with existing states (p0 songs with B > b)
            for (int p0 = 0; p0 <= m - k; ++p0) {
                if (dp[p0].empty()) continue;

                for (auto const& [s0, val0] : dp[p0]) {
                    // Validity check for adding k songs of requirement b
                    // to a state of p0 songs with requirements > b.
                    // This is s0 + i*b <= R(p0+i) for i=1...k
                    // Due to concavity, we only need to check endpoints i=1 and i=k.
                    if (s0 + (long long)b > r[p0 + 1]) {
                        // The condition fails for k=1, so it will fail for any larger k too.
                        // We can break from the s0 loop and go to the next p0.
                        // However, a simple continue is also correct.
                        continue;
                    }
                    if (s0 + (long long)k * b > r[p0 + k]) {
                        continue;
                    }

                    int p = p0 + k;
                    int s = s0 + k * b;
                    
                    // Update DP table for the new state
                    if (next_dp[p].find(s) == next_dp[p].end() || next_dp[p][s] < val0 + current_c_sum) {
                        next_dp[p][s] = val0 + current_c_sum;
                    }
                }
            }
        }
        dp = next_dp;
    }

    long long max_excitement = 0;
    for (int p = 0; p <= m; ++p) {
        for (auto const& [s, val] : dp[p]) {
            max_excitement = max(max_excitement, val);
        }
    }

    cout << max_excitement << endl;

    return 0;
}

提出情報

コンパイルエラー

Main.cpp: In function ‘int main()’:
Main.cpp:66:27: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   66 |         for (int k = 1; k <= songs_by_b[b].size(); ++k) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~

ジャッジ結果