CF1398D-Colored Rectangles
题目:
题目描述:
You are given three multisets of pairs of colored sticks:
- $ R $ pairs of red sticks, the first pair has length $ r_1 $ , the second pair has length $ r_2 $ , $ \dots $ , the $ R $ -th pair has length $ r_R $ ;
- $ G $ pairs of green sticks, the first pair has length $ g_1 $ , the second pair has length $ g_2 $ , $ \dots $ , the $ G $ -th pair has length $ g_G $ ;
- $ B $ pairs of blue sticks, the first pair has length $ b_1 $ , the second pair has length $ b_2 $ , $ \dots $ , the $ B $ -th pair has length $ b_B $ ;
You are constructing rectangles from these pairs of sticks with the following process:
- take a pair of sticks of one color;
- take a pair of sticks of another color different from the first one;
- add the area of the resulting rectangle to the total area.
Thus, you get such rectangles that their opposite sides are the same color and their adjacent sides are not the same color.
Each pair of sticks can be used at most once, some pairs can be left unused. You are not allowed to split a pair into independent sticks.
What is the maximum area you can achieve?
输入格式:
The first line contains three integers $ R $ , $ G $ , $ B $ ( $ 1 \le R, G, B \le 200 $ ) — the number of pairs of red sticks, the number of pairs of green sticks and the number of pairs of blue sticks.
The second line contains $ R $ integers $ r_1, r_2, \dots, r_R $ ( $ 1 \le r_i \le 2000 $ ) — the lengths of sticks in each pair of red sticks.
The third line contains $ G $ integers $ g_1, g_2, \dots, g_G $ ( $ 1 \le g_i \le 2000 $ ) — the lengths of sticks in each pair of green sticks.
The fourth line contains $ B $ integers $ b_1, b_2, \dots, b_B $ ( $ 1 \le b_i \le 2000 $ ) — the lengths of sticks in each pair of blue sticks.
输出格式:
Print the maximum possible total area of the constructed rectangles.
样例:
样例输入 1:
样例输出 1:
样例输入 2:
1
2
3
4
| 2 1 3
9 5
1
2 8 5
|
样例输出 2:
样例输入 3:
1
2
3
4
| 10 1 1
11 7 20 15 19 14 2 4 13 14
8
11
|
样例输出 3:
思路:
实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
| /*
*User: ybw051114
*Time: 2020.08.14 22:35:09
*/
#include <bits/stdc++.h>
using namespace std;
#ifndef use_ios11
#define use_ios11
using namespace std;
struct ins
{
int ans;
ins() { ans = 1; }
#define endl '\n'
void read()
{
}
void read1(char &s)
{
char c = getchar();
for (; !isprint(c) || c == ' ' || c == '\n' || c == '\t'; c = getchar())
;
s = c;
if (c == EOF)
ans = 0;
}
void read1(string &s)
{
s = "";
char c = getchar();
for (; !isprint(c) || c == ' ' || c == '\n' || c == '\t'; c = getchar())
;
for (; isprint(c) && c != ' ' && c != '\n' && c != '\t'; c = getchar())
s += c;
if (c == EOF)
ans = 0;
}
template <typename T>
void read1(T &n)
{
T x = 0;
int f = 1;
char c = getchar();
for (; !isdigit(c); c = getchar())
{
if (c == '-')
f = -1;
if (c == EOF)
{
ans = 0;
return;
}
}
for (; isdigit(c); c = getchar())
x = x * 10 + c - 48;
n = x * f;
if (c == EOF)
ans = 0;
if (c != '.')
return;
T l = 0.1;
while ((c = getchar()) <= '9' && c >= '0')
x = x + (c & 15) * l, l *= 0.1;
n = x * f;
if (c == EOF)
ans = 0;
}
void write() {}
void write1(string s)
{
int n = s.size();
for (int i = 0; i < n; i++)
putchar(s[i]);
}
void write1(const char *s)
{
int n = strlen(s);
for (int i = 0; i < n; i++)
putchar(s[i]);
}
void write1(char s) { putchar(s); }
void write1(float s, int x = 6)
{
char y[10001];
sprintf(y, "%%.%df", x);
printf(y, s);
}
void write1(double s, int x = 6)
{
char y[10001];
sprintf(y, "%%.%dlf", x);
printf(y, s);
}
void write1(long double s, int x = 6)
{
char y[10001];
sprintf(y, "%%.%dLf", x);
printf(y, s);
}
template <typename T>
void write1(T n)
{
if (n < 0)
n = -n, putchar('-');
if (n > 9)
write1(n / 10);
putchar('0' + n % 10);
}
template <typename T>
friend ins operator>>(ins x, T &n);
template <typename T>
friend ins operator<<(ins x, T n);
operator bool() { return ans; }
};
template <typename T>
ins operator>>(ins x, T &n)
{
if (!x.ans)
return x;
x.read1(n);
return x;
}
template <typename T>
ins operator<<(ins x, T n)
{
x.write1(n);
return x;
}
ins yin;
ins yout;
#endif
long long ans = 0;
int a[2001], b[2001], c[2001];
int n, m, q;
long long f[201][201][201];
int main()
{
yin >> n >> m >> q;
for (int i = 1; i <= n; i++)
yin >> a[i];
for (int i = 1; i <= m; i++)
yin >> b[i];
for (int i = 1; i <= q; i++)
yin >> c[i];
sort(a + 1, a + n + 1, greater<int>());
sort(b + 1, b + m + 1, greater<int>());
sort(c + 1, c + q + 1, greater<int>());
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= m; j++)
{
for (int k = 0; k <= q; k++)
{
if (i && j)
f[i][j][k] = max(f[i][j][k], f[i - 1][j - 1][k] + a[i] * b[j]);
if (i && k)
f[i][j][k] = max(f[i][j][k], f[i - 1][j][k - 1] + a[i] * c[k]);
if (k && j)
f[i][j][k] = max(f[i][j][k], f[i][j - 1][k - 1] + b[j] * c[k]);
ans = max(ans, f[i][j][k]);
}
}
}
yout << ans << endl;
return 0;
}
|