#PU623. USACO 2016 February Contest, Gold — Problem 3. Fenced In
USACO 2016 February Contest, Gold — Problem 3. Fenced In
USACO 2016 February Contest, Gold — Problem 3. Fenced In
题目描述
Farmer John has realized that many of his cows are strangely agoraphobic (being
fearful of large open spaces). To try and make them less afraid of grazing, he
partitions his large field into a number of smaller regions by building
vertical (north-south) and horizontal (east-west) fences.
The large field is a rectangle with corner points at and . FJ
builds vertical fences () at distinct locations
(); each fence runs from to .
He also builds horizontal fences () at locations
(); each such fence runs from to
. Each vertical fence crosses through each horizontal fence,
subdividing the large field into a total of regions.
Unfortunately, FJ completely forgot to build gates into his fences, making it
impossible for cows to leave their enclosing region and travel around the entire
field! He wants to remedy this situation by removing pieces of some of his
fences to allow cows to travel between adjacent regions. He wants to select
certain pairs of adjacent regions and remove the entire length of fence
separating them; afterwards, he wants cows to be able to wander through these
openings so they can travel anywhere in his larger field.
For example, FJ might take a fence pattern looking like this:
+---+--+
| | |
+---+--+
| | |
| | |
+---+--+
and open it up like so:
+---+--+
| |
+---+ +
| |
| |
+---+--+
Please help FJ determine the minimum total length of fencing he must remove to
accomplish his goal.
输入格式
The first line of input contains , , , and (). The next lines contain , and the next lines after that contain .
输出格式
Please write the minimum length of fencing FJ must remove. Note that this might be too large to fit into a standard 32-bit integer, so you may need to use 64-bit integer types (e.g., "long long" in C/C++).
数据范围
(见题面原文)
样例
样例 1
15 15 5 2
2
5
10
6
4
11
3
44
Problem credits: Brian Dean