# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
482287 | 2021-10-24T02:16:14 Z | Olympia | Cloud Computing (CEOI18_clo) | C++17 | 364 ms | 1356 KB |
#include <cmath> #include <iostream> #include <set> #include <climits> #include <algorithm> #include <vector> #include <iomanip> #include <type_traits> #include <string> #include <queue> #include <map> using namespace std; struct Order { long long price; //price we gain long long clockspeed; //clockspeed long long cores; //cores we gain }; bool comp (Order o1, Order o2) { if (o1.clockspeed != o2.clockspeed) { return (o1.clockspeed > o2.clockspeed); } return (o1.price < o2.price); } void print(Order a) { cout << "PRICE: " << a.price << endl; cout << "CLOCKSPEED: " << a.clockspeed << endl; cout << "CORES " << a.cores << endl; cout << "------\n"; } int main() { int n; cin >> n; vector<Order> v; for (int i = 0; i < n; i++) { Order a; cin >> a.cores >> a.clockspeed >> a.price; a.price = -a.price; v.push_back(a); } int m; cin >> m; for (int i = 0; i < m; i++) { Order a; cin >> a.cores >> a.clockspeed >> a.price; a.cores = -a.cores; v.push_back(a); } sort(v.begin(), v.end(), comp); vector<long long> dp ((int)1e5 + 10); for (int i = 0; i < dp.size(); i++) { dp[i] = -LLONG_MAX/3; } dp[0] = 0; long long myMax = 0; for (auto p: v) { if (p.cores > 0 ) { //buy a computer for (int i = dp.size() - 1; i >= 0; i--) { if (i - abs(p.cores) < 0) continue; dp[i] = max(dp[i], dp[i - abs(p.cores)] - abs(p.price)); } } else { //customer for (int i = 0; i < dp.size(); i++) { if (i + abs(p.cores) >= dp.size()) continue; dp[i] = max(dp[i], dp[i + abs(p.cores)] + abs(p.price)); } } } for (int i = 0; i < dp.size(); i++) { myMax = max(myMax, dp[i]); } cout << myMax << endl; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 972 KB | Output is correct |
2 | Correct | 1 ms | 972 KB | Output is correct |
3 | Correct | 10 ms | 1088 KB | Output is correct |
4 | Correct | 21 ms | 1096 KB | Output is correct |
5 | Correct | 171 ms | 1164 KB | Output is correct |
6 | Correct | 172 ms | 1100 KB | Output is correct |
7 | Correct | 192 ms | 1100 KB | Output is correct |
8 | Correct | 183 ms | 1164 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 972 KB | Output is correct |
2 | Correct | 2 ms | 972 KB | Output is correct |
3 | Correct | 10 ms | 1092 KB | Output is correct |
4 | Correct | 11 ms | 1092 KB | Output is correct |
5 | Correct | 92 ms | 1108 KB | Output is correct |
6 | Correct | 90 ms | 1100 KB | Output is correct |
7 | Correct | 182 ms | 1220 KB | Output is correct |
8 | Correct | 180 ms | 1160 KB | Output is correct |
9 | Correct | 173 ms | 1100 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 972 KB | Output is correct |
2 | Correct | 3 ms | 972 KB | Output is correct |
3 | Correct | 18 ms | 1100 KB | Output is correct |
4 | Correct | 17 ms | 1104 KB | Output is correct |
5 | Correct | 33 ms | 1100 KB | Output is correct |
6 | Correct | 38 ms | 1100 KB | Output is correct |
7 | Correct | 51 ms | 1152 KB | Output is correct |
8 | Correct | 47 ms | 1100 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 972 KB | Output is correct |
2 | Correct | 2 ms | 972 KB | Output is correct |
3 | Correct | 140 ms | 1100 KB | Output is correct |
4 | Correct | 160 ms | 1100 KB | Output is correct |
5 | Correct | 332 ms | 1228 KB | Output is correct |
6 | Correct | 358 ms | 1228 KB | Output is correct |
7 | Correct | 361 ms | 1348 KB | Output is correct |
8 | Correct | 347 ms | 1228 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 972 KB | Output is correct |
2 | Correct | 16 ms | 1108 KB | Output is correct |
3 | Correct | 77 ms | 1120 KB | Output is correct |
4 | Correct | 178 ms | 1164 KB | Output is correct |
5 | Correct | 357 ms | 1268 KB | Output is correct |
6 | Correct | 364 ms | 1252 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 972 KB | Output is correct |
2 | Correct | 1 ms | 972 KB | Output is correct |
3 | Correct | 10 ms | 1088 KB | Output is correct |
4 | Correct | 21 ms | 1096 KB | Output is correct |
5 | Correct | 171 ms | 1164 KB | Output is correct |
6 | Correct | 172 ms | 1100 KB | Output is correct |
7 | Correct | 192 ms | 1100 KB | Output is correct |
8 | Correct | 183 ms | 1164 KB | Output is correct |
9 | Correct | 1 ms | 972 KB | Output is correct |
10 | Correct | 2 ms | 972 KB | Output is correct |
11 | Correct | 10 ms | 1092 KB | Output is correct |
12 | Correct | 11 ms | 1092 KB | Output is correct |
13 | Correct | 92 ms | 1108 KB | Output is correct |
14 | Correct | 90 ms | 1100 KB | Output is correct |
15 | Correct | 182 ms | 1220 KB | Output is correct |
16 | Correct | 180 ms | 1160 KB | Output is correct |
17 | Correct | 173 ms | 1100 KB | Output is correct |
18 | Correct | 3 ms | 972 KB | Output is correct |
19 | Correct | 3 ms | 972 KB | Output is correct |
20 | Correct | 18 ms | 1100 KB | Output is correct |
21 | Correct | 17 ms | 1104 KB | Output is correct |
22 | Correct | 33 ms | 1100 KB | Output is correct |
23 | Correct | 38 ms | 1100 KB | Output is correct |
24 | Correct | 51 ms | 1152 KB | Output is correct |
25 | Correct | 47 ms | 1100 KB | Output is correct |
26 | Correct | 2 ms | 972 KB | Output is correct |
27 | Correct | 2 ms | 972 KB | Output is correct |
28 | Correct | 140 ms | 1100 KB | Output is correct |
29 | Correct | 160 ms | 1100 KB | Output is correct |
30 | Correct | 332 ms | 1228 KB | Output is correct |
31 | Correct | 358 ms | 1228 KB | Output is correct |
32 | Correct | 361 ms | 1348 KB | Output is correct |
33 | Correct | 347 ms | 1228 KB | Output is correct |
34 | Correct | 1 ms | 972 KB | Output is correct |
35 | Correct | 16 ms | 1108 KB | Output is correct |
36 | Correct | 77 ms | 1120 KB | Output is correct |
37 | Correct | 178 ms | 1164 KB | Output is correct |
38 | Correct | 357 ms | 1268 KB | Output is correct |
39 | Correct | 364 ms | 1252 KB | Output is correct |
40 | Correct | 93 ms | 1128 KB | Output is correct |
41 | Correct | 179 ms | 1100 KB | Output is correct |
42 | Correct | 276 ms | 1348 KB | Output is correct |
43 | Correct | 347 ms | 1308 KB | Output is correct |
44 | Correct | 355 ms | 1320 KB | Output is correct |
45 | Correct | 349 ms | 1356 KB | Output is correct |
46 | Correct | 178 ms | 1188 KB | Output is correct |
47 | Correct | 272 ms | 1280 KB | Output is correct |
48 | Correct | 258 ms | 1228 KB | Output is correct |