Overview

Select some songs so that the total playback time is at least \(K\) seconds, and minimize the maximum number of consecutive songs of the same genre (the bias score).

The key insight is that the “bias score based on arrangement” depends only on how many songs are selected from each genre, and can be considered independently of the songs’ playback times.

Analysis

For a given selection of songs, count the number of selected songs per genre.

• Let \(S\) be the total number of selected songs
• Let \(C\) be the maximum number of songs selected from any single genre

Then, the minimum bias score is

\[ \left\lceil \frac{C}{S-C+1} \right\rceil \]

Why this formula holds

Consider the genre with the most selected songs. It has \(C\) songs.

The remaining songs number \(S-C\).
Using these as separators, the maximum number of positions where songs of the most frequent genre can be placed is

\[ S-C+1 \]

For example, if songs of other genres are denoted by x, then:

_ x _ x _ x _

There are positions available before, after, and between them.

Even if we distribute the \(C\) songs of the most frequent genre as evenly as possible among these \(S-C+1\) positions, at least one position must contain

\[ \left\lceil \frac{C}{S-C+1} \right\rceil \]

songs.

Therefore, the bias score cannot be less than this value.
Moreover, it is actually possible to arrange the songs so that this value is not exceeded.

Hence, if we know the total number of selected songs \(S\) and the maximum number of songs selected from a single genre \(C\), we can compute the minimum bias score.

---

Next, consider the playback time.

If we decide to select \(t\) songs from a certain genre, to maximize the total playback time, we should choose the \(t\) songs with the longest playback times from that genre.

Therefore, for each genre, we sort the songs in descending order of playback time and maintain prefix sums for the total when selecting the first \(t\) songs.

---

Naively enumerating all subsets of songs would result in

\[ 2^{300} \]

possibilities (since the maximum number of candidate songs is \(2N=300\)), which is far too many.

Instead, we focus only on “how many songs to select from each genre” and use DP to find the maximum total playback time.

Algorithm

Let the number of candidate songs be \(M=2N\).

1. Group songs by genre

For each genre, sort the playback times in descending order.

For example, if a genre has songs with playback times

\[ [10, 3, 8] \]

we sort them in descending order:

\[ [10, 8, 3] \]

Then we compute the prefix sums:

\[ [0, 10, 18, 21] \]

This allows us to immediately retrieve the maximum total playback time when selecting \(t\) songs from that genre.

---

2. Enumerate the maximum selection count \(C\)

We consider \(C\) as the upper limit: “select at most \(C\) songs from any single genre.”

We examine \(C=1,2,\dots,M\).

---

3. Use DP to find “the maximum playback time when selecting a total of \(S\) songs”

Define the DP as follows:

\[ dp[s] = \text{maximum playback time when selecting a total of } s \text{ songs from genres seen so far} \]

For each genre, we transition by choosing \(t\) songs from that genre.

However, for the current \(C\), the number of songs selectable from each genre is at most \(C\), so:

\[ 0 \leq t \leq \min(\text{number of songs in that genre}, C) \]

The transition is as follows:

\[ ndp[s+t] = \max(ndp[s+t], dp[s] + \text{prefix}[t]) \]

Here, \(\text{prefix}[t]\) is the maximum total playback time when selecting \(t\) songs from that genre.

---

4. Update the bias score if the condition is satisfied

From the DP result, if selecting a total of \(S\) songs yields a playback time of at least \(K\), then the bias score is

\[ \left\lceil \frac{C}{S-C+1} \right\rceil \]

In the code, the ceiling division is computed as:

\[ \frac{C + (S-C+1) - 1}{S-C+1} \]

int denom = S - C + 1;
int score = (C + denom - 1) / denom;

This is used as a candidate to update the minimum answer.

---

5. Output -1 if even selecting all songs gives less than \(K\)

First, compute the total playback time of all songs.

If the total is less than \(K\) even when all songs are selected, then it is impossible to create a playlist satisfying the condition, so output -1.

Complexity

• Time complexity: \(O(M^3) = O(N^3)\)
• Space complexity: \(O(M) = O(N)\)

where \(M=2N\).

Since \(N \leq 150\), we have \(M \leq 300\), which runs sufficiently fast.

Implementation Notes

• Within each genre, sort songs in descending order of playback time.

• By computing prefix sums for each genre, “the maximum total when selecting \(t\) songs from that genre” can be obtained in \(O(1)\).

• The DP array is initialized to \(-\infty\) each time.

• Since the total playback time and DP values can become large, use long long.

• If the answer becomes \(1\), it cannot be reduced further, so the search can be terminated early.

  Source Code

#include <bits/stdc++.h>
using namespace std;

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

    int N;
    long long K;
    cin >> N >> K;

    int M = 2 * N;
    vector<vector<int>> songs(M + 1);
    long long total = 0;

    for (int i = 0; i < M; i++) {
        int B, A;
        cin >> B >> A;
        songs[B].push_back(A);
        total += A;
    }

    if (total < K) {
        cout << -1 << '\n';
        return 0;
    }

    vector<vector<long long>> pref;
    for (auto &v : songs) {
        if (v.empty()) continue;
        sort(v.begin(), v.end(), greater<int>());
        vector<long long> p(v.size() + 1, 0);
        for (int i = 0; i < (int)v.size(); i++) {
            p[i + 1] = p[i] + v[i];
        }
        pref.push_back(move(p));
    }

    const long long NEG = -(1LL << 60);
    int ans = M;

    vector<long long> dp(M + 1), ndp(M + 1);

    for (int C = 1; C <= M; C++) {
        fill(dp.begin(), dp.end(), NEG);
        dp[0] = 0;
        int used = 0;

        for (const auto &p : pref) {
            int len = (int)p.size() - 1;
            int lim = min(len, C);

            fill(ndp.begin(), ndp.end(), NEG);

            for (int s = 0; s <= used; s++) {
                if (dp[s] == NEG) continue;
                for (int t = 0; t <= lim; t++) {
                    ndp[s + t] = max(ndp[s + t], dp[s] + p[t]);
                }
            }

            used += lim;
            dp.swap(ndp);
        }

        for (int S = C; S <= used; S++) {
            if (dp[S] >= K) {
                int denom = S - C + 1;
                int score = (C + denom - 1) / denom;
                ans = min(ans, score);
            }
        }

        if (ans == 1) break;
    }

    cout << ans << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.5-xhigh.