Bike Parking

Sanne recently conceived a lucrative business idea: renting out premium bike parking at the Eindhoven train station. To maximize her profits, she divided the bike parking slots into \(N\) different tiers, numbered from \(0\) to \(N-1\). Tier 0, the premium tier, is located very close to the train platforms. Higher-numbered tiers consist of parking slots that are worse (the higher the tier, the worse the slot). The number of slots in tier \(t\) is \(x_t\).

Users parking their bikes are assigned their parking slot via an app. Each user has a subscription level and expects a parking slot in the corresponding tier. However, the terms of service do not guarantee users a slot in their respective tier.

If a user with subscription level \(s\) is assigned a slot in tier \(t\), then one of the following three things happens:
- If \(t < s\), the user will be happy and upvote the app.
- If \(t = s\), the user will be satisfied and will not do anything.
- If \(t > s\), the user will be angry and downvote the app.

Today, Sanne's app has \(y_0+y_1+\ldots+y_{N-1}\) users, where \(y_s\) is the number of users with subscription level \(s\). She needs your help to assign the users to the parking slots. Each user should get exactly one slot. No slot can be assigned to more than one user, but it is okay for some parking slots to not be assigned to any users. Furthermore, the total number of users does not exceed the total number of available parking slots.

Sanne wants to maximize the rating of her app. Let \(U\) be the number of upvotes and \(D\) be the number of downvotes. Your task is to maximize \(U-D\).

(An illustrative figure from the official statement is omitted here.)

• \(1 \leq N \leq 3 \cdot 10^5\).
• \(0 \leq x_i, y_i \leq 10^9\) for \(i = 0,1,\ldots , N-1\).
• \(y_0+y_1+\ldots + y_{N-1} \leq x_0+x_1+\ldots + x_{N-1} \leq 10^9\).

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group, you need to solve all test cases in the test group.

Group | Score | Limits 1 | 16 | \(N=2, x_i \leq 100, y_i \leq 100\) 2 | 9 | \(x_i = x_j = y_i = y_j\) for all \(i,j\). In other words all the \(x\)'s and \(y\)'s in the input are the same. 3 | 19 | \(x_i, y_i \leq 1\) 4 | 24 | \(N,x_i,y_i \leq 100\) 5 | 32 | No additional constraints.

The first line contains one integer \(N\), the number of tiers or subscription levels.

The second line contains \(N\) integers \(x_0, x_1, \ldots, x_{N-1}\), the number of slots in the different tiers.

The third line contains \(N\) integers \(y_0, y_1, \ldots, y_{N-1}\), the number of users with each subscription level.

Output one integer, the maximum possible value of \(U-D\) by assigning the users to parking slots optimally.

rip 작성

출처 EGOI 2024