#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
struct Event {
enum Type { Processor, Task };
Type type;
int cores, frequency, price;
Event(Type type, int cores, int frequency, int price)
: type(type), cores(cores), frequency(frequency), price(price) { }
};
const int MAXN = 2005, MAXC = 55, MAXDP = MAXN*MAXC;
const long long int INF = 1000000000000000000LL; // 10^18
int n,m;
vector<Event> events;
long long int dp[MAXDP];
bool comp(const Event& event1, const Event& event2) {
if (event1.frequency == event2.frequency)
return event1.type < event2.type;
return event1.frequency > event2.frequency;
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
int c,f,v;
scanf("%d%d%d", &c, &f, &v);
events.push_back(Event(Event::Processor,c,f,v));
}
scanf("%d", &m);
for (int i = 0; i < m; ++i) {
int c,f,v;
scanf("%d%d%d", &c, &f, &v);
events.push_back(Event(Event::Task,c,f,v));
}
sort(events.begin(), events.end(), comp);
for (int i = 0; i < MAXDP; ++i)
dp[i] = -INF;
dp[0] = 0;
for (int i = 0; i < (int)events.size(); ++i)
if (events[i].type == Event::Processor)
for (int j = MAXDP-1; j >= 0; --j) {
int index = j + events[i].cores;
long long int value = dp[j] - events[i].price;
if (index < MAXDP && dp[index] < value)
dp[index] = value;
}
else
for (int j = 0; j < MAXDP; ++j) {
int index = j - events[i].cores;
long long int value = dp[j] + events[i].price;
if (index >= 0 && dp[j] != -INF && dp[index] < value)
dp[index] = value;
}
long long int result = 0;
for (int i = 0; i < MAXDP; ++i)
result = max(result, dp[i]);
printf("%lld\n", result);
}
Compilation message
clo.cpp: In function 'int main()':
clo.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
28 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
clo.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
31 | scanf("%d%d%d", &c, &f, &v);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
clo.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
34 | scanf("%d", &m);
| ~~~~~^~~~~~~~~~
clo.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
37 | scanf("%d%d%d", &c, &f, &v);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1116 KB |
Output is correct |
2 |
Correct |
1 ms |
1116 KB |
Output is correct |
3 |
Correct |
8 ms |
1116 KB |
Output is correct |
4 |
Correct |
15 ms |
1204 KB |
Output is correct |
5 |
Correct |
133 ms |
1372 KB |
Output is correct |
6 |
Correct |
135 ms |
1372 KB |
Output is correct |
7 |
Correct |
144 ms |
1368 KB |
Output is correct |
8 |
Correct |
151 ms |
1368 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1116 KB |
Output is correct |
2 |
Correct |
1 ms |
1116 KB |
Output is correct |
3 |
Correct |
8 ms |
1116 KB |
Output is correct |
4 |
Correct |
8 ms |
1196 KB |
Output is correct |
5 |
Correct |
69 ms |
1116 KB |
Output is correct |
6 |
Correct |
67 ms |
1308 KB |
Output is correct |
7 |
Correct |
166 ms |
1536 KB |
Output is correct |
8 |
Correct |
141 ms |
1372 KB |
Output is correct |
9 |
Correct |
165 ms |
1116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1116 KB |
Output is correct |
2 |
Correct |
3 ms |
1116 KB |
Output is correct |
3 |
Correct |
13 ms |
1300 KB |
Output is correct |
4 |
Correct |
13 ms |
1116 KB |
Output is correct |
5 |
Correct |
26 ms |
1208 KB |
Output is correct |
6 |
Correct |
27 ms |
1116 KB |
Output is correct |
7 |
Correct |
45 ms |
1116 KB |
Output is correct |
8 |
Correct |
47 ms |
1112 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1116 KB |
Output is correct |
2 |
Correct |
2 ms |
1116 KB |
Output is correct |
3 |
Correct |
106 ms |
1328 KB |
Output is correct |
4 |
Correct |
127 ms |
1344 KB |
Output is correct |
5 |
Correct |
335 ms |
1368 KB |
Output is correct |
6 |
Correct |
409 ms |
1432 KB |
Output is correct |
7 |
Correct |
424 ms |
1432 KB |
Output is correct |
8 |
Correct |
426 ms |
1428 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1116 KB |
Output is correct |
2 |
Correct |
12 ms |
1116 KB |
Output is correct |
3 |
Correct |
61 ms |
1116 KB |
Output is correct |
4 |
Correct |
138 ms |
1112 KB |
Output is correct |
5 |
Correct |
354 ms |
1624 KB |
Output is correct |
6 |
Correct |
398 ms |
1368 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1116 KB |
Output is correct |
2 |
Correct |
1 ms |
1116 KB |
Output is correct |
3 |
Correct |
8 ms |
1116 KB |
Output is correct |
4 |
Correct |
15 ms |
1204 KB |
Output is correct |
5 |
Correct |
133 ms |
1372 KB |
Output is correct |
6 |
Correct |
135 ms |
1372 KB |
Output is correct |
7 |
Correct |
144 ms |
1368 KB |
Output is correct |
8 |
Correct |
151 ms |
1368 KB |
Output is correct |
9 |
Correct |
1 ms |
1116 KB |
Output is correct |
10 |
Correct |
1 ms |
1116 KB |
Output is correct |
11 |
Correct |
8 ms |
1116 KB |
Output is correct |
12 |
Correct |
8 ms |
1196 KB |
Output is correct |
13 |
Correct |
69 ms |
1116 KB |
Output is correct |
14 |
Correct |
67 ms |
1308 KB |
Output is correct |
15 |
Correct |
166 ms |
1536 KB |
Output is correct |
16 |
Correct |
141 ms |
1372 KB |
Output is correct |
17 |
Correct |
165 ms |
1116 KB |
Output is correct |
18 |
Correct |
3 ms |
1116 KB |
Output is correct |
19 |
Correct |
3 ms |
1116 KB |
Output is correct |
20 |
Correct |
13 ms |
1300 KB |
Output is correct |
21 |
Correct |
13 ms |
1116 KB |
Output is correct |
22 |
Correct |
26 ms |
1208 KB |
Output is correct |
23 |
Correct |
27 ms |
1116 KB |
Output is correct |
24 |
Correct |
45 ms |
1116 KB |
Output is correct |
25 |
Correct |
47 ms |
1112 KB |
Output is correct |
26 |
Correct |
2 ms |
1116 KB |
Output is correct |
27 |
Correct |
2 ms |
1116 KB |
Output is correct |
28 |
Correct |
106 ms |
1328 KB |
Output is correct |
29 |
Correct |
127 ms |
1344 KB |
Output is correct |
30 |
Correct |
335 ms |
1368 KB |
Output is correct |
31 |
Correct |
409 ms |
1432 KB |
Output is correct |
32 |
Correct |
424 ms |
1432 KB |
Output is correct |
33 |
Correct |
426 ms |
1428 KB |
Output is correct |
34 |
Correct |
1 ms |
1116 KB |
Output is correct |
35 |
Correct |
12 ms |
1116 KB |
Output is correct |
36 |
Correct |
61 ms |
1116 KB |
Output is correct |
37 |
Correct |
138 ms |
1112 KB |
Output is correct |
38 |
Correct |
354 ms |
1624 KB |
Output is correct |
39 |
Correct |
398 ms |
1368 KB |
Output is correct |
40 |
Correct |
77 ms |
1308 KB |
Output is correct |
41 |
Correct |
151 ms |
1112 KB |
Output is correct |
42 |
Correct |
210 ms |
1372 KB |
Output is correct |
43 |
Correct |
337 ms |
1436 KB |
Output is correct |
44 |
Correct |
320 ms |
1368 KB |
Output is correct |
45 |
Correct |
314 ms |
1476 KB |
Output is correct |
46 |
Correct |
137 ms |
1116 KB |
Output is correct |
47 |
Correct |
243 ms |
1372 KB |
Output is correct |
48 |
Correct |
219 ms |
1420 KB |
Output is correct |