SegmentDrawing
SRM 634 · 2014-08-25 · by lg5293
Problem Statement
You have N distinct points in the plane. The points are labeled 0 through N-1. No three of the points are collinear. For each i, point i lies at (x[i], y[i]).
You are going to score some points by coloring the points and connecting them by straight line segments. The process will consist of two phases. In the first phase you will color each point either red or blue. In the second phase you are allowed to draw zero or more segments. Each segment must connect two points of the same color. Each segment must be drawn in the same color as the points it connects. Segments of the same color can touch and intersect each other freely. However, differently colored segments must be completely disjoint. (In other words, no red segment may touch or intersect a blue segment.)
A red segment between points i and j gives you redScore[i * N + j] points. A blue segment between points i and j gives you blueScore[i * N + j] points. Your total score is the sum of points obtained for all the segments you have drawn.
You are given the
Constraints
- N will be between 2 and 20, inclusive.
- x will contain exactly N elements.
- y will contain exactly N elements.
- Each element of x and y will be between -1000 and 1000, inclusive.
- All points will be distinct.
- No three points will be collinear.
- redScore will contain exactly N^2 elements.
- blueScore will contain exactly N^2 elements.
- Each element of redScore and blueScore will be between 0 and 100,000, inclusive.
- redScore[i * N + i] will be zero for all 0 <= i < N.
- blueScore[i * N + i] will be zero for all 0 <= i < N.
- redScore[i * N + j] = redScore[j * N + i] for all 0 <= i,j < N.
- blueScore[i * N + j] = blueScore[j * N + i] for all 0 <= i,j < N.
{0,1,0,-1}
{1,0,-1,0}
{0, 1, 2, 3,
1, 0, 6, 4,
2, 6, 0, 5,
3, 4, 5, 0}
{0, 2, 3, 7,
2, 0, 4, 6,
3, 4, 0, 5,
7, 6, 5, 0}
Returns: 27
Here, we can color all the points blue and then draw all possible blue segments. Our score is then 2+3+7+4+6+5=27, which is the maximum we can get.
{0, 1}
{1, 0}
{0, 101, 101, 0}
{0, 100, 100, 0}
Returns: 101
{-3, -1, -1, 1, 1, 3}
{ 0, -2, 2, -2, 2, 0}
{0, 2, 1, 2, 1, 2,
2, 0, 2, 1, 2, 1,
1, 2, 0, 2, 1, 2,
2, 1, 2, 0, 2, 1,
1, 2, 1, 2, 0, 2,
2, 1, 2, 1, 2, 0}
{0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0,
0, 0, 0, 21, 0, 0,
0, 0, 21, 0, 0, 0,
0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0}
Returns: 25
{-100, 100, 0, -10, 10, 0}
{0, 0, 100, 10, 10, 1}
{ 0, 96, 96, 25, 25, 25,
96, 0, 96, 25, 25, 25,
96, 96, 0, 25, 25, 25,
25, 25, 25, 0, 10, 10,
25, 25, 25, 10, 0, 10,
25, 25, 25, 10, 10, 0}
{ 0, 30, 30, 20, 20, 20,
30, 0, 30, 20, 20, 20,
30, 30, 0, 20, 20, 20,
20, 20, 20, 0, 86, 86,
20, 20, 20, 86, 0, 86,
20, 20, 20, 86, 86, 0}
Returns: 546
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
{1, 4, 9, 16, 25, 36, 49, 64, 81, 100}
{0, 15, 2, 3, 4, 5, 6, 7, 8, 9,
15, 0, 15, 2, 3, 4, 5, 6, 7, 8,
2, 15, 0, 15, 2, 3, 4, 5, 6, 7,
3, 2, 15, 0, 15, 2, 3, 4, 5, 6,
4, 3, 2, 15, 0, 15, 2, 3, 4, 5,
5, 4, 3, 2, 15, 0, 15, 2, 3, 4,
6, 5, 4, 3, 2, 15, 0, 15, 2, 3,
7, 6, 5, 4, 3, 2, 15, 0, 15, 2,
8, 7, 6, 5, 4, 3, 2, 15, 0, 15,
9, 8, 7, 6, 5, 4, 3, 2, 15, 0}
{0, 0, 2, 3, 4, 5, 6, 7, 8, 9,
0, 0, 0, 2, 3, 4, 5, 6, 7, 8,
2, 0, 0, 0, 2, 3, 4, 5, 6, 7,
3, 2, 0, 0, 0, 2, 3, 4, 5, 6,
4, 3, 2, 0, 0, 100, 2, 3, 4, 5,
5, 4, 3, 2, 100, 0, 0, 2, 3, 4,
6, 5, 4, 3, 2, 0, 0, 0, 2, 3,
7, 6, 5, 4, 3, 2, 0, 0, 0, 2,
8, 7, 6, 5, 4, 3, 2, 0, 0, 0,
9, 8, 7, 6, 5, 4, 3, 2, 0, 0}
Returns: 300
Submissions are judged against all 54 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SegmentDrawing with a public method int maxScore(vector<int> x, vector<int> y, vector<int> redScore, vector<int> blueScore) · 54 test cases · 2 s / 256 MB per case