Created
March 21, 2020 16:00
-
-
Save dariost/e0d3e076d230836e27788c140627ce1f to your computer and use it in GitHub Desktop.
Quaranterry 2020 solutions
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <bits/stdc++.h> | |
using namespace std; | |
int64_t fastexp(int64_t b, int64_t e) { | |
if(e == 0) { | |
return 1; | |
} else if(e % 2 == 1) { | |
return b * fastexp(b, e - 1); | |
} else { | |
int64_t tmp = fastexp(b, e / 2); | |
return tmp * tmp; | |
} | |
} | |
int main() { | |
size_t T; | |
cin >> T; | |
for(size_t caso = 1; caso <= T; caso++) { | |
size_t n; | |
int64_t v, y, k; | |
cin >> n >> v >> y >> k; | |
vector<int64_t> h(n); | |
for(size_t i = 0; i < n; i++) { | |
cin >> h[i]; | |
} | |
vector<int64_t> prefix(n + 1); | |
prefix[0] = 0; | |
for(size_t i = 0; i < n; i++) { | |
prefix[i + 1] = prefix[i] + h[i]; | |
} | |
vector<vector<int64_t>> memo(n, vector<int64_t>(n, -1LL)); | |
vector<vector<char>> choice(n, vector<char>(n)); | |
function<int64_t(size_t, size_t)> f = [&f, &memo, &choice, &h, &v, &k, &y, &n, &prefix](size_t index, | |
size_t upgrade) -> int64_t { | |
if(index >= n) { | |
return 0; | |
} | |
if(memo[index][upgrade] >= 0) { | |
return memo[index][upgrade]; | |
} | |
int64_t speed = v * fastexp(2LL, min(upgrade, 20UL)); | |
int64_t budget = prefix[index] - k * upgrade; | |
int64_t a_choice = h[index] / speed + (h[index] % speed != 0) + f(index + 1, upgrade); | |
memo[index][upgrade] = a_choice; | |
choice[index][upgrade] = 'A'; | |
int64_t e_choice = y + f(index + 3, upgrade); | |
if(e_choice < memo[index][upgrade]) { | |
memo[index][upgrade] = e_choice; | |
choice[index][upgrade] = 'E'; | |
} | |
if(budget >= k) { | |
speed *= 2LL; | |
int64_t i_choice = h[index] / speed + (h[index] % speed != 0) + f(index + 1, upgrade + 1); | |
if(i_choice < memo[index][upgrade]) { | |
memo[index][upgrade] = i_choice; | |
choice[index][upgrade] = 'I'; | |
} | |
} | |
return memo[index][upgrade]; | |
}; | |
f(0, 0); | |
string sol; | |
size_t i = 0; | |
size_t upg = 0; | |
while(i < n) { | |
sol.push_back(choice[i][upg]); | |
if(choice[i][upg] == 'A') { | |
i++; | |
} else if(choice[i][upg] == 'I') { | |
i++; | |
upg++; | |
} else if(choice[i][upg] == 'E') { | |
i += 3; | |
} else { | |
assert(!"UNREACHABLE"); | |
} | |
} | |
cout << "Case #" << caso << ": " << sol << endl; | |
} | |
return EXIT_SUCCESS; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <bits/stdc++.h> | |
using namespace std; | |
int main() { | |
size_t T; | |
cin >> T; | |
for(size_t caso = 1; caso <= T; caso++) { | |
size_t n, q; | |
cin >> n >> q; | |
vector<uint64_t> v(n); | |
for(size_t i = 0; i < n; i++) { | |
cin >> v[i]; | |
} | |
sort(v.begin(), v.end()); | |
uint64_t best = ULLONG_MAX; | |
uint64_t index = -1; | |
for(size_t i = 0; i < q; i++) { | |
uint64_t z; | |
cin >> z; | |
if(z <= v[0]) { | |
if(v.back() - z < best) { | |
best = v.back() - z; | |
index = i; | |
} | |
} else if(z >= v.back()) { | |
if(z - v[0] < best) { | |
best = z - v[0]; | |
index = i; | |
} | |
} else { | |
uint64_t sol = min(z - v[0], v.back() - z) + v.back() - v[0]; | |
if(sol < best) { | |
best = sol; | |
index = i; | |
} | |
} | |
} | |
cout << "Case #" << caso << ": " << index + 1 << endl; | |
} | |
return EXIT_SUCCESS; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <bits/stdc++.h> | |
using namespace std; | |
int main() { | |
size_t T; | |
cin >> T; | |
for(size_t caso = 1; caso <= T; caso++) { | |
size_t n; | |
cin >> n; | |
vector<int> a(n), b(n); | |
for(size_t i = 0; i < n; i++) { | |
cin >> a[i]; | |
} | |
for(size_t i = 0; i < n; i++) { | |
cin >> b[i]; | |
} | |
sort(a.begin(), a.end()); | |
sort(b.begin(), b.end()); | |
reverse(a.begin(), a.end()); | |
int sol = 0; | |
for(size_t i = 0; i < n; i++) { | |
sol += max(b[i] - a[i], 0); | |
} | |
cout << "Case #" << caso << ": " << sol << endl; | |
} | |
return EXIT_SUCCESS; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <bits/stdc++.h> | |
using namespace std; | |
using is = pair<int64_t, size_t>; | |
using vis = vector<is>; | |
int main() { | |
size_t T; | |
cin >> T; | |
for(size_t caso = 1; caso <= T; caso++) { | |
size_t n, m, k; | |
cin >> n >> m >> k; | |
vector<vis> children(n); | |
for(size_t i = 0; i < m; i++) { | |
size_t a, b; | |
int64_t c; | |
cin >> a >> b >> c; | |
a--; | |
b--; | |
children[a].emplace_back(c, b); | |
children[b].emplace_back(c, a); | |
} | |
vector<int64_t> ticket(k); | |
for(size_t i = 0; i < k; i++) { | |
cin >> ticket[i]; | |
} | |
sort(ticket.begin(), ticket.end()); | |
ticket.push_back(0); | |
priority_queue<is, vis, greater<is>> pq; | |
vector<int64_t> cost(n * (k + 1), LLONG_MAX); | |
pq.emplace(0, 0); | |
while(!pq.empty()) { | |
auto top = pq.top(); | |
pq.pop(); | |
if(cost[top.second] <= top.first) { | |
continue; | |
} | |
cost[top.second] = top.first; | |
size_t node = top.second % n; | |
size_t level = top.second / n; | |
for(size_t i = 0; i < children[node].size(); i++) { | |
if(top.first + children[node][i].first < cost[children[node][i].second + n * level]) { | |
pq.emplace(top.first + children[node][i].first, children[node][i].second + n * level); | |
} | |
if(level < k) { | |
if(top.first < cost[children[node][i].second + n * (level + 1)]) { | |
pq.emplace(top.first, children[node][i].second + n * (level + 1)); | |
} | |
} | |
} | |
} | |
int64_t best = LLONG_MAX; | |
int64_t prefix = accumulate(ticket.begin(), ticket.end(), 0LL); | |
for(size_t i = 0; i <= k; i++) { | |
best = min(best, cost[(n - 1) + n * i] - prefix); | |
prefix -= ticket[i]; | |
} | |
cout << "Case #" << caso << ": " << best << endl; | |
} | |
return EXIT_SUCCESS; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <bits/stdc++.h> | |
using namespace std; | |
int main() { | |
size_t T; | |
cin >> T; | |
for(size_t caso = 1; caso <= T; caso++) { | |
uint64_t n; | |
cin >> n; | |
if(n <= 2) { | |
cout << "Case #" << caso << ": -1" << endl; | |
} else { | |
cout << "Case #" << caso << ": " << 0 << " " << 1 << " " << n - 1 << endl; | |
} | |
} | |
return EXIT_SUCCESS; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment