| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 2048 MB | 120 | 43 | 36 | 34.615% |
Deep in the countryside, Farmer John’s cows aren’t just ordinary farm animals—they are part of a clandestine bovine intelligence network. Each cow carries an ID number, carefully assigned by the elite cow cryptographers. However, due to Farmer John's rather haphazard tagging system, some cows ended up with the same ID.
Farmer John noted that there are $N$ (1ドル\le N\le 2\cdot 10^5$) unique ID numbers, and for each unique ID $d_i$ (0ドル\le d_i\le 10^9$), there are $n_i$ (1ドル\le n_i\le 10^9$) cows who shared it.
The cows can only communicate in pairs, and their secret encryption method has one strict rule: two cows can only exchange information if they are not the same cow and the sum of their ID numbers equals either $A$ or $B$ (0ドル\le A\le B\le 2\cdot 10^9$). A cow can only engage in one conversation at a time (i.e., no cow can be part of more than one pair).
Farmer John would like to maximize the number of disjoint communication pairs to ensure the best information flow. Can you determine the largest number of conversations that can happen at once?
The first line contains $N,ドル $A,ドル $B$.
The next $N$ lines each contain $n_i$ and $d_i$. No two $d_i$ are the same.
The maximum number of disjoint communicating pairs that can be formed at the same time.
Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).
4 4 5 17 2 100 0 10 1 200 4
118
A cow with an ID of 0ドル$ can communicate with another cow with an ID of 4ドル$ because the sum of their IDs is 4ドル$. Since there are a total of 100ドル$ cows of ID 0ドル$ and 200ドル$ cows of ID 4ドル,ドル there can be up to 100ドル$ communicating pairs with this combination of IDs.
A cow with an ID of 4ドル$ can also communicate with another cow with an ID of 1ドル$ (sum to 5ドル$). There are 10ドル$ cows of ID 1ドル$ and 100ドル$ remaining unpaired cows of ID 4ドル,ドル allowing for another 10ドル$ pairs.
Finally, a cow with an ID of 2ドル$ can communicate with another cow of the same ID. Since there are a total of 17ドル$ cows of ID 2ドル,ドル there can be up to 8ドル$ more pairs.
In total, there are 100ドル+10+8=118$ communicating pairs. It can be shown that this is the maximum possible number of pairs.
4 4 5 100 0 10 1 100 3 20 4
30
Pairing IDs 0ドル$ and 4ドル$ makes 20ドル$ pairs, while pairing IDs 1ドル$ and 3ドル$ makes 10ドル$ pairs. It can be shown that this is the optimal pairing, resulting in a total of 30ドル$ pairs.