#include <bits/stdc++.h>
using namespace std;
typedef long long int LL;
const LL INF = 1e15;
struct Event {
int cores;
int freq;
int value;
int id;
Event(int cores_, int freq_, int value_, int id_):
cores(cores_), freq(freq_), value(value_), id(id_) {}
bool operator<(const Event& other) const {
if (freq != other.freq) return freq > other.freq;
return id < other.id;
}
};
int n, m;
vector<Event> events;
vector<LL> DP;
int main() {
int cores_available = 0;
cin >> n;
for (int i = 0; i < n; i++) {
int cores, freq, price;
cin >> cores >> freq >> price;
cores_available += cores;
events.push_back(Event(cores, freq, price, -1));
}
cin >> m;
for (int i = 0; i < m; i++) {
int cores, freq, reward;
cin >> cores >> freq >> reward;
events.push_back(Event(cores, freq, reward, i));
}
sort(events.begin(), events.end());
DP.resize(cores_available + 1, -INF);
DP[0] = 0;
for (const Event& evt : events) {
if (evt.id == -1) {
for (int i = cores_available; i >= evt.cores; i--)
DP[i] = max(DP[i], DP[i - evt.cores] - evt.value);
}
else {
for (int i = 0; i <= cores_available - evt.cores; i++)
DP[i] = max(DP[i], DP[i + evt.cores] + evt.value);
}
}
LL result = -1;
for (int i = 0; i <= cores_available; i++)
result = max(result, DP[i]);
cout << result << "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
248 KB |
Output is correct |
2 |
Correct |
3 ms |
392 KB |
Output is correct |
3 |
Correct |
2 ms |
420 KB |
Output is correct |
4 |
Correct |
3 ms |
464 KB |
Output is correct |
5 |
Correct |
6 ms |
512 KB |
Output is correct |
6 |
Correct |
8 ms |
512 KB |
Output is correct |
7 |
Correct |
7 ms |
516 KB |
Output is correct |
8 |
Correct |
10 ms |
588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
588 KB |
Output is correct |
2 |
Correct |
3 ms |
596 KB |
Output is correct |
3 |
Correct |
4 ms |
596 KB |
Output is correct |
4 |
Correct |
3 ms |
596 KB |
Output is correct |
5 |
Correct |
25 ms |
740 KB |
Output is correct |
6 |
Correct |
4 ms |
744 KB |
Output is correct |
7 |
Correct |
118 ms |
996 KB |
Output is correct |
8 |
Correct |
30 ms |
996 KB |
Output is correct |
9 |
Correct |
200 ms |
1252 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1252 KB |
Output is correct |
2 |
Correct |
2 ms |
1252 KB |
Output is correct |
3 |
Correct |
3 ms |
1252 KB |
Output is correct |
4 |
Correct |
3 ms |
1252 KB |
Output is correct |
5 |
Correct |
3 ms |
1252 KB |
Output is correct |
6 |
Correct |
4 ms |
1252 KB |
Output is correct |
7 |
Correct |
4 ms |
1252 KB |
Output is correct |
8 |
Correct |
4 ms |
1252 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1252 KB |
Output is correct |
2 |
Correct |
3 ms |
1252 KB |
Output is correct |
3 |
Correct |
12 ms |
1252 KB |
Output is correct |
4 |
Correct |
5 ms |
1252 KB |
Output is correct |
5 |
Correct |
236 ms |
1252 KB |
Output is correct |
6 |
Correct |
384 ms |
1404 KB |
Output is correct |
7 |
Correct |
439 ms |
1404 KB |
Output is correct |
8 |
Correct |
457 ms |
1404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1404 KB |
Output is correct |
2 |
Correct |
3 ms |
1404 KB |
Output is correct |
3 |
Correct |
24 ms |
1404 KB |
Output is correct |
4 |
Correct |
9 ms |
1404 KB |
Output is correct |
5 |
Correct |
391 ms |
1404 KB |
Output is correct |
6 |
Correct |
393 ms |
1404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
248 KB |
Output is correct |
2 |
Correct |
3 ms |
392 KB |
Output is correct |
3 |
Correct |
2 ms |
420 KB |
Output is correct |
4 |
Correct |
3 ms |
464 KB |
Output is correct |
5 |
Correct |
6 ms |
512 KB |
Output is correct |
6 |
Correct |
8 ms |
512 KB |
Output is correct |
7 |
Correct |
7 ms |
516 KB |
Output is correct |
8 |
Correct |
10 ms |
588 KB |
Output is correct |
9 |
Correct |
3 ms |
588 KB |
Output is correct |
10 |
Correct |
3 ms |
596 KB |
Output is correct |
11 |
Correct |
4 ms |
596 KB |
Output is correct |
12 |
Correct |
3 ms |
596 KB |
Output is correct |
13 |
Correct |
25 ms |
740 KB |
Output is correct |
14 |
Correct |
4 ms |
744 KB |
Output is correct |
15 |
Correct |
118 ms |
996 KB |
Output is correct |
16 |
Correct |
30 ms |
996 KB |
Output is correct |
17 |
Correct |
200 ms |
1252 KB |
Output is correct |
18 |
Correct |
2 ms |
1252 KB |
Output is correct |
19 |
Correct |
2 ms |
1252 KB |
Output is correct |
20 |
Correct |
3 ms |
1252 KB |
Output is correct |
21 |
Correct |
3 ms |
1252 KB |
Output is correct |
22 |
Correct |
3 ms |
1252 KB |
Output is correct |
23 |
Correct |
4 ms |
1252 KB |
Output is correct |
24 |
Correct |
4 ms |
1252 KB |
Output is correct |
25 |
Correct |
4 ms |
1252 KB |
Output is correct |
26 |
Correct |
3 ms |
1252 KB |
Output is correct |
27 |
Correct |
3 ms |
1252 KB |
Output is correct |
28 |
Correct |
12 ms |
1252 KB |
Output is correct |
29 |
Correct |
5 ms |
1252 KB |
Output is correct |
30 |
Correct |
236 ms |
1252 KB |
Output is correct |
31 |
Correct |
384 ms |
1404 KB |
Output is correct |
32 |
Correct |
439 ms |
1404 KB |
Output is correct |
33 |
Correct |
457 ms |
1404 KB |
Output is correct |
34 |
Correct |
3 ms |
1404 KB |
Output is correct |
35 |
Correct |
3 ms |
1404 KB |
Output is correct |
36 |
Correct |
24 ms |
1404 KB |
Output is correct |
37 |
Correct |
9 ms |
1404 KB |
Output is correct |
38 |
Correct |
391 ms |
1404 KB |
Output is correct |
39 |
Correct |
393 ms |
1404 KB |
Output is correct |
40 |
Correct |
26 ms |
1404 KB |
Output is correct |
41 |
Correct |
78 ms |
1404 KB |
Output is correct |
42 |
Correct |
11 ms |
1404 KB |
Output is correct |
43 |
Correct |
446 ms |
1532 KB |
Output is correct |
44 |
Correct |
483 ms |
1532 KB |
Output is correct |
45 |
Correct |
404 ms |
1532 KB |
Output is correct |
46 |
Correct |
7 ms |
1532 KB |
Output is correct |
47 |
Correct |
12 ms |
1532 KB |
Output is correct |
48 |
Correct |
13 ms |
1532 KB |
Output is correct |