#include <iostream>
#include <vector>
#include <algorithm>
#define PB push_back
using namespace std;
typedef long long ll;
const ll INF = 1e15;
const int maxn = 1e5 + 100;
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.PB (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 |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
3 ms |
504 KB |
Output is correct |
3 |
Correct |
2 ms |
560 KB |
Output is correct |
4 |
Correct |
2 ms |
608 KB |
Output is correct |
5 |
Correct |
5 ms |
608 KB |
Output is correct |
6 |
Correct |
5 ms |
752 KB |
Output is correct |
7 |
Correct |
6 ms |
752 KB |
Output is correct |
8 |
Correct |
8 ms |
828 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
828 KB |
Output is correct |
2 |
Correct |
2 ms |
828 KB |
Output is correct |
3 |
Correct |
2 ms |
828 KB |
Output is correct |
4 |
Correct |
2 ms |
828 KB |
Output is correct |
5 |
Correct |
25 ms |
928 KB |
Output is correct |
6 |
Correct |
4 ms |
928 KB |
Output is correct |
7 |
Correct |
110 ms |
1348 KB |
Output is correct |
8 |
Correct |
24 ms |
1348 KB |
Output is correct |
9 |
Correct |
175 ms |
1704 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1704 KB |
Output is correct |
2 |
Correct |
2 ms |
1704 KB |
Output is correct |
3 |
Correct |
2 ms |
1704 KB |
Output is correct |
4 |
Correct |
3 ms |
1704 KB |
Output is correct |
5 |
Correct |
3 ms |
1704 KB |
Output is correct |
6 |
Correct |
2 ms |
1704 KB |
Output is correct |
7 |
Correct |
3 ms |
1704 KB |
Output is correct |
8 |
Correct |
3 ms |
1704 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1704 KB |
Output is correct |
2 |
Correct |
2 ms |
1704 KB |
Output is correct |
3 |
Correct |
10 ms |
1704 KB |
Output is correct |
4 |
Correct |
4 ms |
1704 KB |
Output is correct |
5 |
Correct |
202 ms |
1704 KB |
Output is correct |
6 |
Correct |
376 ms |
1876 KB |
Output is correct |
7 |
Correct |
433 ms |
1920 KB |
Output is correct |
8 |
Correct |
350 ms |
1968 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1968 KB |
Output is correct |
2 |
Correct |
2 ms |
1968 KB |
Output is correct |
3 |
Correct |
24 ms |
1968 KB |
Output is correct |
4 |
Correct |
8 ms |
1968 KB |
Output is correct |
5 |
Correct |
356 ms |
2080 KB |
Output is correct |
6 |
Correct |
369 ms |
2132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
3 ms |
504 KB |
Output is correct |
3 |
Correct |
2 ms |
560 KB |
Output is correct |
4 |
Correct |
2 ms |
608 KB |
Output is correct |
5 |
Correct |
5 ms |
608 KB |
Output is correct |
6 |
Correct |
5 ms |
752 KB |
Output is correct |
7 |
Correct |
6 ms |
752 KB |
Output is correct |
8 |
Correct |
8 ms |
828 KB |
Output is correct |
9 |
Correct |
3 ms |
828 KB |
Output is correct |
10 |
Correct |
2 ms |
828 KB |
Output is correct |
11 |
Correct |
2 ms |
828 KB |
Output is correct |
12 |
Correct |
2 ms |
828 KB |
Output is correct |
13 |
Correct |
25 ms |
928 KB |
Output is correct |
14 |
Correct |
4 ms |
928 KB |
Output is correct |
15 |
Correct |
110 ms |
1348 KB |
Output is correct |
16 |
Correct |
24 ms |
1348 KB |
Output is correct |
17 |
Correct |
175 ms |
1704 KB |
Output is correct |
18 |
Correct |
2 ms |
1704 KB |
Output is correct |
19 |
Correct |
2 ms |
1704 KB |
Output is correct |
20 |
Correct |
2 ms |
1704 KB |
Output is correct |
21 |
Correct |
3 ms |
1704 KB |
Output is correct |
22 |
Correct |
3 ms |
1704 KB |
Output is correct |
23 |
Correct |
2 ms |
1704 KB |
Output is correct |
24 |
Correct |
3 ms |
1704 KB |
Output is correct |
25 |
Correct |
3 ms |
1704 KB |
Output is correct |
26 |
Correct |
3 ms |
1704 KB |
Output is correct |
27 |
Correct |
2 ms |
1704 KB |
Output is correct |
28 |
Correct |
10 ms |
1704 KB |
Output is correct |
29 |
Correct |
4 ms |
1704 KB |
Output is correct |
30 |
Correct |
202 ms |
1704 KB |
Output is correct |
31 |
Correct |
376 ms |
1876 KB |
Output is correct |
32 |
Correct |
433 ms |
1920 KB |
Output is correct |
33 |
Correct |
350 ms |
1968 KB |
Output is correct |
34 |
Correct |
2 ms |
1968 KB |
Output is correct |
35 |
Correct |
2 ms |
1968 KB |
Output is correct |
36 |
Correct |
24 ms |
1968 KB |
Output is correct |
37 |
Correct |
8 ms |
1968 KB |
Output is correct |
38 |
Correct |
356 ms |
2080 KB |
Output is correct |
39 |
Correct |
369 ms |
2132 KB |
Output is correct |
40 |
Correct |
36 ms |
2132 KB |
Output is correct |
41 |
Correct |
69 ms |
2132 KB |
Output is correct |
42 |
Correct |
13 ms |
2132 KB |
Output is correct |
43 |
Correct |
420 ms |
2316 KB |
Output is correct |
44 |
Correct |
448 ms |
2432 KB |
Output is correct |
45 |
Correct |
406 ms |
2432 KB |
Output is correct |
46 |
Correct |
7 ms |
2432 KB |
Output is correct |
47 |
Correct |
20 ms |
2432 KB |
Output is correct |
48 |
Correct |
10 ms |
2432 KB |
Output is correct |