#include <iostream>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
constexpr int N = 105;
constexpr int LG = 41;
int64_t shit[10];
std::vector<std::pair<std::string, int64_t>> dp[N][LG];
void clear_vec(int s, std::vector<std::pair<std::string, int64_t>>& vec) {
if (vec.empty()) {
return;
}
std::sort(vec.begin(), vec.end());
std::list<std::remove_reference_t<decltype(vec[0])>> list(vec.rbegin(), vec.rend());
std::vector<int> prf1;
auto check = [&](const auto& it, const auto& it2) {
if (it.second <= it2.second) {
// return true;
bool fk = true;
int sz = std::min(it.first.size(), it2.first.size());
for (int t = 0, sm2 = 0; t < sz; t++) {
// sm1 += it.first[t];
sm2 += it2.first[t];
fk &= prf1[t] >= sm2;
}
return fk;
}
return false;
};
// for (int k : std::array{10, 10}) {
for (int k : std::array{20, 100, 200}) {
for (auto it = std::prev(list.end());; it--) {
int dlt = 0;
prf1.assign(it->first.size(), 0);
for (int t = 0, s = 0; t < it->first.size(); t++) {
s += it->first[t];
prf1[t] = s;
}
for (auto it2 = std::next(it); dlt < k && it2 != list.end(); it2++) {
if (check(*it, *it2)) {
it2--;
list.erase(std::next(it2));
} else {
dlt++;
}
}
if (it == list.begin()) {
break;
}
}
}
vec.assign(list.begin(), list.end());
vec.shrink_to_fit();
}
void clear_vec2(int s, std::vector<std::pair<std::string, int64_t>>& vec) {
std::sort(vec.begin(), vec.end());
// std::sort(vec.rbegin(), vec.rend());
auto check = [&](const auto& it, const auto& it2) {
if (it.second <= it2.second) {
bool fk = true;
int sz = std::min(it.first.size(), it2.first.size());
for (int t = 0, sm1 = 0, sm2 = 0; t < sz; t++) {
sm1 += it.first[t];
sm2 += it2.first[t];
fk &= sm1 >= sm2;
}
return fk;
}
return false;
};
std::remove_reference_t<decltype(vec)> vec2;
while (vec.size() > 0) {
auto p = vec.back();
vec.pop_back();
while (vec.size() > 0) {
if (check(p, vec.back())) {
vec.pop_back();
continue;
}
if (vec.size() > 1 && check(p, vec.rbegin()[1])) {
vec.erase(vec.end() - 2);
continue;
}
if (vec.size() > 2 && check(p, vec.rbegin()[2])) {
vec.erase(vec.end() - 3);
continue;
}
break;
}
vec2.push_back(p);
}
vec.swap(vec2);
vec.shrink_to_fit();
}
int32_t main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int n = 0;
int t;
std::cin >> t;
std::vector<std::vector<int>> inputs(t);
for (auto& vec : inputs) {
int k;
std::cin >> k;
vec.resize(k);
for (auto& i : vec) {
std::cin >> i;
}
n = std::max(n, k);
}
dp[1][0] = {{std::string(1, 1), 0}};
for (int s = 2; s <= n; s++) {
std::vector<int> ord(s - 1);
std::iota(ord.begin(), ord.end(), 1);
std::sort(ord.begin(), ord.end(), [&](int a, int b) { return abs(a - s / 2) < abs(b - s / 2); });
for (int k = 0; k < LG; k++) {
static std::unordered_map<std::string, int64_t> map;
// static __gnu_pbds::cc_hash_table<std::string, int64_t> map;
map.clear();
for (int k1 = 0; k1 < LG; k1++) {
for (int k2 = 0; k2 < LG; k2++) {
if (k != std::max(k1, k2) + 1) {
continue;
}
for (int s1 : ord) {
int s2 = s - s1;
if (dp[s1][k1].empty() || dp[s2][k2].empty()) {
continue;
}
if (k >= LG) {
continue;
}
for (auto [v1, c1] : dp[s1][k1]) {
for (auto [v2, c2] : dp[s2][k2]) {
v2.resize(std::max(v2.size(), v1.size() + 1));
for (int i = 0; i < v1.size(); i++) {
v2[i + 1] += v1[i];
}
int64_t cost = c1 + c2 + ((1LL << k1) - 1) + ((1LL << k2) - 1);
auto [it, suc] = map.insert({v2, cost});
if (!suc) {
it->second = std::min(it->second, cost);
}
}
}
}
// auto& vec = dp[s][k];
// vec.assign(map.begin(), map.end());
// clear_vec(s, dp[s][k]);
// map.clear();
// for (auto [s, v] : vec) {
// map[s] = v;
// }
}
}
auto& vec = dp[s][k];
vec.assign(map.begin(), map.end());
clear_vec(s, dp[s][k]);
}
{
int i = s;
std::cerr << i << " ";
// std::cerr << i << " ";
// for (int j = 0; j < LG; j++) {
// std::cerr << dp[i][j].size() << " \n"[j == LG - 1];
// }
std::cerr.flush();
}
}
int64_t total_sum = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < LG; j++) {
total_sum += dp[i][j].size();
}
}
for (int i = 1; i <= n; i++) {
int s = 0;
for (int j = 0; j < LG; j++) {
for (auto [a, b] : dp[i][j]) {
s += std::min<int>(20, a.size()) + 4;
}
}
std::cerr << s << "\n";
}
std::cerr << "total: " << total_sum << std::endl;
std::cerr << shit[0] << " " << shit[1] << "\n";
for (auto& vec : inputs) {
int m = vec.size();
int64_t ans = 1e18;
std::sort(vec.begin(), vec.end());
for (int k = 0; k < LG; k++) {
for (auto [vc2, ct] : dp[m][k]) {
std::vector<char> vc;
for (int i = 0; i < vc2.size(); i++) {
vc.insert(vc.end(), vc2[i], i);
}
int64_t res = 0;
res += ct;
for (int i = 0; i < m; i++) {
res += vec.rbegin()[i] * int64_t(vc[i]);
}
ans = std::min(ans, res);
}
}
std::cout << ans << "\n";
}
return 0;
}
#include <iostream>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
constexpr int N = 105;
constexpr int LG = 41;
int64_t shit[10];
std::vector<std::pair<std::string, int64_t>> dp[N][LG];
void clear_vec(int s, std::vector<std::pair<std::string, int64_t>>& vec) {
if (vec.empty()) {
return;
}
std::sort(vec.begin(), vec.end());
std::list<std::remove_reference_t<decltype(vec[0])>> list(vec.rbegin(), vec.rend());
std::vector<int> prf1;
auto check = [&](const auto& it, const auto& it2) {
if (it.second <= it2.second) {
// return true;
bool fk = true;
int sz = std::min(it.first.size(), it2.first.size());
for (int t = 0, sm2 = 0; t < sz; t++) {
// sm1 += it.first[t];
sm2 += it2.first[t];
fk &= prf1[t] >= sm2;
}
return fk;
}
return false;
};
// for (int k : std::array{10, 10}) {
for (int k : std::array{20, 100, 200}) {
for (auto it = std::prev(list.end());; it--) {
int dlt = 0;
prf1.assign(it->first.size(), 0);
for (int t = 0, s = 0; t < it->first.size(); t++) {
s += it->first[t];
prf1[t] = s;
}
for (auto it2 = std::next(it); dlt < k && it2 != list.end(); it2++) {
if (check(*it, *it2)) {
it2--;
list.erase(std::next(it2));
} else {
dlt++;
}
}
if (it == list.begin()) {
break;
}
}
}
vec.assign(list.begin(), list.end());
vec.shrink_to_fit();
}
void clear_vec2(int s, std::vector<std::pair<std::string, int64_t>>& vec) {
std::sort(vec.begin(), vec.end());
// std::sort(vec.rbegin(), vec.rend());
auto check = [&](const auto& it, const auto& it2) {
if (it.second <= it2.second) {
bool fk = true;
int sz = std::min(it.first.size(), it2.first.size());
for (int t = 0, sm1 = 0, sm2 = 0; t < sz; t++) {
sm1 += it.first[t];
sm2 += it2.first[t];
fk &= sm1 >= sm2;
}
return fk;
}
return false;
};
std::remove_reference_t<decltype(vec)> vec2;
while (vec.size() > 0) {
auto p = vec.back();
vec.pop_back();
while (vec.size() > 0) {
if (check(p, vec.back())) {
vec.pop_back();
continue;
}
if (vec.size() > 1 && check(p, vec.rbegin()[1])) {
vec.erase(vec.end() - 2);
continue;
}
if (vec.size() > 2 && check(p, vec.rbegin()[2])) {
vec.erase(vec.end() - 3);
continue;
}
break;
}
vec2.push_back(p);
}
vec.swap(vec2);
vec.shrink_to_fit();
}
int32_t main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int n = 0;
int t;
std::cin >> t;
std::vector<std::vector<int>> inputs(t);
for (auto& vec : inputs) {
int k;
std::cin >> k;
vec.resize(k);
for (auto& i : vec) {
std::cin >> i;
}
n = std::max(n, k);
}
dp[1][0] = {{std::string(1, 1), 0}};
for (int s = 2; s <= n; s++) {
std::vector<int> ord(s - 1);
std::iota(ord.begin(), ord.end(), 1);
std::sort(ord.begin(), ord.end(), [&](int a, int b) { return abs(a - s / 2) < abs(b - s / 2); });
for (int k = 0; k < LG; k++) {
static std::unordered_map<std::string, int64_t> map;
// static __gnu_pbds::cc_hash_table<std::string, int64_t> map;
map.clear();
for (int k1 = 0; k1 < LG; k1++) {
for (int k2 = 0; k2 < LG; k2++) {
if (k != std::max(k1, k2) + 1) {
continue;
}
for (int s1 : ord) {
int s2 = s - s1;
if (dp[s1][k1].empty() || dp[s2][k2].empty()) {
continue;
}
if (k >= LG) {
continue;
}
for (auto [v1, c1] : dp[s1][k1]) {
for (auto [v2, c2] : dp[s2][k2]) {
v2.resize(std::max(v2.size(), v1.size() + 1));
for (int i = 0; i < v1.size(); i++) {
v2[i + 1] += v1[i];
}
int64_t cost = c1 + c2 + ((1LL << k1) - 1) + ((1LL << k2) - 1);
auto [it, suc] = map.insert({v2, cost});
if (!suc) {
it->second = std::min(it->second, cost);
}
}
}
}
// auto& vec = dp[s][k];
// vec.assign(map.begin(), map.end());
// clear_vec(s, dp[s][k]);
// map.clear();
// for (auto [s, v] : vec) {
// map[s] = v;
// }
}
}
auto& vec = dp[s][k];
vec.assign(map.begin(), map.end());
clear_vec(s, dp[s][k]);
}
{
int i = s;
std::cerr << i << " ";
// std::cerr << i << " ";
// for (int j = 0; j < LG; j++) {
// std::cerr << dp[i][j].size() << " \n"[j == LG - 1];
// }
std::cerr.flush();
}
}
int64_t total_sum = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < LG; j++) {
total_sum += dp[i][j].size();
}
}
for (int i = 1; i <= n; i++) {
int s = 0;
for (int j = 0; j < LG; j++) {
for (auto [a, b] : dp[i][j]) {
s += std::min<int>(20, a.size()) + 4;
}
}
std::cerr << s << "\n";
}
std::cerr << "total: " << total_sum << std::endl;
std::cerr << shit[0] << " " << shit[1] << "\n";
for (auto& vec : inputs) {
int m = vec.size();
int64_t ans = 1e18;
std::sort(vec.begin(), vec.end());
for (int k = 0; k < LG; k++) {
for (auto [vc2, ct] : dp[m][k]) {
std::vector<char> vc;
for (int i = 0; i < vc2.size(); i++) {
vc.insert(vc.end(), vc2[i], i);
}
int64_t res = 0;
res += ct;
for (int i = 0; i < m; i++) {
res += vec.rbegin()[i] * int64_t(vc[i]);
}
ans = std::min(ans, res);
}
}
std::cout << ans << "\n";
}
return 0;
}
#include <iostream>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
constexpr int N = 105;
constexpr int LG = 41;
int64_t shit[10];
std::vector<std::pair<std::string, int64_t>> dp[N][LG];
void clear_vec(int s, std::vector<std::pair<std::string, int64_t>>& vec) {
if (vec.empty()) {
return;
}
std::sort(vec.begin(), vec.end());
std::list<std::remove_reference_t<decltype(vec[0])>> list(vec.rbegin(), vec.rend());
std::vector<int> prf1;
auto check = [&](const auto& it, const auto& it2) {
if (it.second <= it2.second) {
// return true;
bool fk = true;
int sz = std::min(it.first.size(), it2.first.size());
for (int t = 0, sm2 = 0; t < sz; t++) {
// sm1 += it.first[t];
sm2 += it2.first[t];
fk &= prf1[t] >= sm2;
}
return fk;
}
return false;
};
// for (int k : std::array{10, 10}) {
for (int k : std::array{20, 100, 200}) {
for (auto it = std::prev(list.end());; it--) {
int dlt = 0;
prf1.assign(it->first.size(), 0);
for (int t = 0, s = 0; t < it->first.size(); t++) {
s += it->first[t];
prf1[t] = s;
}
for (auto it2 = std::next(it); dlt < k && it2 != list.end(); it2++) {
if (check(*it, *it2)) {
it2--;
list.erase(std::next(it2));
} else {
dlt++;
}
}
if (it == list.begin()) {
break;
}
}
}
vec.assign(list.begin(), list.end());
vec.shrink_to_fit();
}
void clear_vec2(int s, std::vector<std::pair<std::string, int64_t>>& vec) {
std::sort(vec.begin(), vec.end());
// std::sort(vec.rbegin(), vec.rend());
auto check = [&](const auto& it, const auto& it2) {
if (it.second <= it2.second) {
bool fk = true;
int sz = std::min(it.first.size(), it2.first.size());
for (int t = 0, sm1 = 0, sm2 = 0; t < sz; t++) {
sm1 += it.first[t];
sm2 += it2.first[t];
fk &= sm1 >= sm2;
}
return fk;
}
return false;
};
std::remove_reference_t<decltype(vec)> vec2;
while (vec.size() > 0) {
auto p = vec.back();
vec.pop_back();
while (vec.size() > 0) {
if (check(p, vec.back())) {
vec.pop_back();
continue;
}
if (vec.size() > 1 && check(p, vec.rbegin()[1])) {
vec.erase(vec.end() - 2);
continue;
}
if (vec.size() > 2 && check(p, vec.rbegin()[2])) {
vec.erase(vec.end() - 3);
continue;
}
break;
}
vec2.push_back(p);
}
vec.swap(vec2);
vec.shrink_to_fit();
}
int32_t main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int n = 0;
int t;
std::cin >> t;
std::vector<std::vector<int>> inputs(t);
for (auto& vec : inputs) {
int k;
std::cin >> k;
vec.resize(k);
for (auto& i : vec) {
std::cin >> i;
}
n = std::max(n, k);
}
dp[1][0] = {{std::string(1, 1), 0}};
for (int s = 2; s <= n; s++) {
std::vector<int> ord(s - 1);
std::iota(ord.begin(), ord.end(), 1);
std::sort(ord.begin(), ord.end(), [&](int a, int b) { return abs(a - s / 2) < abs(b - s / 2); });
for (int k = 0; k < LG; k++) {
static std::unordered_map<std::string, int64_t> map;
// static __gnu_pbds::cc_hash_table<std::string, int64_t> map;
map.clear();
for (int k1 = 0; k1 < LG; k1++) {
for (int k2 = 0; k2 < LG; k2++) {
if (k != std::max(k1, k2) + 1) {
continue;
}
for (int s1 : ord) {
int s2 = s - s1;
if (dp[s1][k1].empty() || dp[s2][k2].empty()) {
continue;
}
if (k >= LG) {
continue;
}
for (auto [v1, c1] : dp[s1][k1]) {
for (auto [v2, c2] : dp[s2][k2]) {
v2.resize(std::max(v2.size(), v1.size() + 1));
for (int i = 0; i < v1.size(); i++) {
v2[i + 1] += v1[i];
}
int64_t cost = c1 + c2 + ((1LL << k1) - 1) + ((1LL << k2) - 1);
auto [it, suc] = map.insert({v2, cost});
if (!suc) {
it->second = std::min(it->second, cost);
}
}
}
}
// auto& vec = dp[s][k];
// vec.assign(map.begin(), map.end());
// clear_vec(s, dp[s][k]);
// map.clear();
// for (auto [s, v] : vec) {
// map[s] = v;
// }
}
}
auto& vec = dp[s][k];
vec.assign(map.begin(), map.end());
clear_vec(s, dp[s][k]);
}
{
int i = s;
std::cerr << i << " ";
// std::cerr << i << " ";
// for (int j = 0; j < LG; j++) {
// std::cerr << dp[i][j].size() << " \n"[j == LG - 1];
// }
std::cerr.flush();
}
}
int64_t total_sum = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < LG; j++) {
total_sum += dp[i][j].size();
}
}
for (int i = 1; i <= n; i++) {
int s = 0;
for (int j = 0; j < LG; j++) {
for (auto [a, b] : dp[i][j]) {
s += std::min<int>(20, a.size()) + 4;
}
}
std::cerr << s << "\n";
}
std::cerr << "total: " << total_sum << std::endl;
std::cerr << shit[0] << " " << shit[1] << "\n";
for (auto& vec : inputs) {
int m = vec.size();
int64_t ans = 1e18;
std::sort(vec.begin(), vec.end());
for (int k = 0; k < LG; k++) {
for (auto [vc2, ct] : dp[m][k]) {
std::vector<char> vc;
for (int i = 0; i < vc2.size(); i++) {
vc.insert(vc.end(), vc2[i], i);
}
int64_t res = 0;
res += ct;
for (int i = 0; i < m; i++) {
res += vec.rbegin()[i] * int64_t(vc[i]);
}
ans = std::min(ans, res);
}
}
std::cout << ans << "\n";
}
return 0;
}
#include <iostream>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
constexpr int N = 105;
constexpr int LG = 41;
int64_t shit[10];
std::vector<std::pair<std::string, int64_t>> dp[N][LG];
void clear_vec(int s, std::vector<std::pair<std::string, int64_t>>& vec) {
if (vec.empty()) {
return;
}
std::sort(vec.begin(), vec.end());
std::list<std::remove_reference_t<decltype(vec[0])>> list(vec.rbegin(), vec.rend());
std::vector<int> prf1;
auto check = [&](const auto& it, const auto& it2) {
if (it.second <= it2.second) {
// return true;
bool fk = true;
int sz = std::min(it.first.size(), it2.first.size());
for (int t = 0, sm2 = 0; t < sz; t++) {
// sm1 += it.first[t];
sm2 += it2.first[t];
fk &= prf1[t] >= sm2;
}
return fk;
}
return false;
};
// for (int k : std::array{10, 10}) {
for (int k : std::array{20, 100, 200}) {
for (auto it = std::prev(list.end());; it--) {
int dlt = 0;
prf1.assign(it->first.size(), 0);
for (int t = 0, s = 0; t < it->first.size(); t++) {
s += it->first[t];
prf1[t] = s;
}
for (auto it2 = std::next(it); dlt < k && it2 != list.end(); it2++) {
if (check(*it, *it2)) {
it2--;
list.erase(std::next(it2));
} else {
dlt++;
}
}
if (it == list.begin()) {
break;
}
}
}
vec.assign(list.begin(), list.end());
vec.shrink_to_fit();
}
void clear_vec2(int s, std::vector<std::pair<std::string, int64_t>>& vec) {
std::sort(vec.begin(), vec.end());
// std::sort(vec.rbegin(), vec.rend());
auto check = [&](const auto& it, const auto& it2) {
if (it.second <= it2.second) {
bool fk = true;
int sz = std::min(it.first.size(), it2.first.size());
for (int t = 0, sm1 = 0, sm2 = 0; t < sz; t++) {
sm1 += it.first[t];
sm2 += it2.first[t];
fk &= sm1 >= sm2;
}
return fk;
}
return false;
};
std::remove_reference_t<decltype(vec)> vec2;
while (vec.size() > 0) {
auto p = vec.back();
vec.pop_back();
while (vec.size() > 0) {
if (check(p, vec.back())) {
vec.pop_back();
continue;
}
if (vec.size() > 1 && check(p, vec.rbegin()[1])) {
vec.erase(vec.end() - 2);
continue;
}
if (vec.size() > 2 && check(p, vec.rbegin()[2])) {
vec.erase(vec.end() - 3);
continue;
}
break;
}
vec2.push_back(p);
}
vec.swap(vec2);
vec.shrink_to_fit();
}
int32_t main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int n = 0;
int t;
std::cin >> t;
std::vector<std::vector<int>> inputs(t);
for (auto& vec : inputs) {
int k;
std::cin >> k;
vec.resize(k);
for (auto& i : vec) {
std::cin >> i;
}
n = std::max(n, k);
}
dp[1][0] = {{std::string(1, 1), 0}};
for (int s = 2; s <= n; s++) {
std::vector<int> ord(s - 1);
std::iota(ord.begin(), ord.end(), 1);
std::sort(ord.begin(), ord.end(), [&](int a, int b) { return abs(a - s / 2) < abs(b - s / 2); });
for (int k = 0; k < LG; k++) {
static std::unordered_map<std::string, int64_t> map;
// static __gnu_pbds::cc_hash_table<std::string, int64_t> map;
map.clear();
for (int k1 = 0; k1 < LG; k1++) {
for (int k2 = 0; k2 < LG; k2++) {
if (k != std::max(k1, k2) + 1) {
continue;
}
for (int s1 : ord) {
int s2 = s - s1;
if (dp[s1][k1].empty() || dp[s2][k2].empty()) {
continue;
}
if (k >= LG) {
continue;
}
for (auto [v1, c1] : dp[s1][k1]) {
for (auto [v2, c2] : dp[s2][k2]) {
v2.resize(std::max(v2.size(), v1.size() + 1));
for (int i = 0; i < v1.size(); i++) {
v2[i + 1] += v1[i];
}
int64_t cost = c1 + c2 + ((1LL << k1) - 1) + ((1LL << k2) - 1);
auto [it, suc] = map.insert({v2, cost});
if (!suc) {
it->second = std::min(it->second, cost);
}
}
}
}
// auto& vec = dp[s][k];
// vec.assign(map.begin(), map.end());
// clear_vec(s, dp[s][k]);
// map.clear();
// for (auto [s, v] : vec) {
// map[s] = v;
// }
}
}
auto& vec = dp[s][k];
vec.assign(map.begin(), map.end());
clear_vec(s, dp[s][k]);
}
{
int i = s;
std::cerr << i << " ";
// std::cerr << i << " ";
// for (int j = 0; j < LG; j++) {
// std::cerr << dp[i][j].size() << " \n"[j == LG - 1];
// }
std::cerr.flush();
}
}
int64_t total_sum = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < LG; j++) {
total_sum += dp[i][j].size();
}
}
for (int i = 1; i <= n; i++) {
int s = 0;
for (int j = 0; j < LG; j++) {
for (auto [a, b] : dp[i][j]) {
s += std::min<int>(20, a.size()) + 4;
}
}
std::cerr << s << "\n";
}
std::cerr << "total: " << total_sum << std::endl;
std::cerr << shit[0] << " " << shit[1] << "\n";
for (auto& vec : inputs) {
int m = vec.size();
int64_t ans = 1e18;
std::sort(vec.begin(), vec.end());
for (int k = 0; k < LG; k++) {
for (auto [vc2, ct] : dp[m][k]) {
std::vector<char> vc;
for (int i = 0; i < vc2.size(); i++) {
vc.insert(vc.end(), vc2[i], i);
}
int64_t res = 0;
res += ct;
for (int i = 0; i < m; i++) {
res += vec.rbegin()[i] * int64_t(vc[i]);
}
ans = std::min(ans, res);
}
}
std::cout << ans << "\n";
}
return 0;
}
#include <iostream>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
constexpr int N = 105;
constexpr int LG = 41;
int64_t shit[10];
std::vector<std::pair<std::string, int64_t>> dp[N][LG];
void clear_vec(int s, std::vector<std::pair<std::string, int64_t>>& vec) {
if (vec.empty()) {
return;
}
std::sort(vec.begin(), vec.end());
std::list<std::remove_reference_t<decltype(vec[0])>> list(vec.rbegin(), vec.rend());
std::vector<int> prf1;
auto check = [&](const auto& it, const auto& it2) {
if (it.second <= it2.second) {
// return true;
bool fk = true;
int sz = std::min(it.first.size(), it2.first.size());
for (int t = 0, sm2 = 0; t < sz; t++) {
// sm1 += it.first[t];
sm2 += it2.first[t];
fk &= prf1[t] >= sm2;
}
return fk;
}
return false;
};
// for (int k : std::array{10, 10}) {
for (int k : std::array{20, 100, 200}) {
for (auto it = std::prev(list.end());; it--) {
int dlt = 0;
prf1.assign(it->first.size(), 0);
for (int t = 0, s = 0; t < it->first.size(); t++) {
s += it->first[t];
prf1[t] = s;
}
for (auto it2 = std::next(it); dlt < k && it2 != list.end(); it2++) {
if (check(*it, *it2)) {
it2--;
list.erase(std::next(it2));
} else {
dlt++;
}
}
if (it == list.begin()) {
break;
}
}
}
vec.assign(list.begin(), list.end());
vec.shrink_to_fit();
}
void clear_vec2(int s, std::vector<std::pair<std::string, int64_t>>& vec) {
std::sort(vec.begin(), vec.end());
// std::sort(vec.rbegin(), vec.rend());
auto check = [&](const auto& it, const auto& it2) {
if (it.second <= it2.second) {
bool fk = true;
int sz = std::min(it.first.size(), it2.first.size());
for (int t = 0, sm1 = 0, sm2 = 0; t < sz; t++) {
sm1 += it.first[t];
sm2 += it2.first[t];
fk &= sm1 >= sm2;
}
return fk;
}
return false;
};
std::remove_reference_t<decltype(vec)> vec2;
while (vec.size() > 0) {
auto p = vec.back();
vec.pop_back();
while (vec.size() > 0) {
if (check(p, vec.back())) {
vec.pop_back();
continue;
}
if (vec.size() > 1 && check(p, vec.rbegin()[1])) {
vec.erase(vec.end() - 2);
continue;
}
if (vec.size() > 2 && check(p, vec.rbegin()[2])) {
vec.erase(vec.end() - 3);
continue;
}
break;
}
vec2.push_back(p);
}
vec.swap(vec2);
vec.shrink_to_fit();
}
int32_t main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int n = 0;
int t;
std::cin >> t;
std::vector<std::vector<int>> inputs(t);
for (auto& vec : inputs) {
int k;
std::cin >> k;
vec.resize(k);
for (auto& i : vec) {
std::cin >> i;
}
n = std::max(n, k);
}
dp[1][0] = {{std::string(1, 1), 0}};
for (int s = 2; s <= n; s++) {
std::vector<int> ord(s - 1);
std::iota(ord.begin(), ord.end(), 1);
std::sort(ord.begin(), ord.end(), [&](int a, int b) { return abs(a - s / 2) < abs(b - s / 2); });
for (int k = 0; k < LG; k++) {
static std::unordered_map<std::string, int64_t> map;
// static __gnu_pbds::cc_hash_table<std::string, int64_t> map;
map.clear();
for (int k1 = 0; k1 < LG; k1++) {
for (int k2 = 0; k2 < LG; k2++) {
if (k != std::max(k1, k2) + 1) {
continue;
}
for (int s1 : ord) {
int s2 = s - s1;
if (dp[s1][k1].empty() || dp[s2][k2].empty()) {
continue;
}
if (k >= LG) {
continue;
}
for (auto [v1, c1] : dp[s1][k1]) {
for (auto [v2, c2] : dp[s2][k2]) {
v2.resize(std::max(v2.size(), v1.size() + 1));
for (int i = 0; i < v1.size(); i++) {
v2[i + 1] += v1[i];
}
int64_t cost = c1 + c2 + ((1LL << k1) - 1) + ((1LL << k2) - 1);
auto [it, suc] = map.insert({v2, cost});
if (!suc) {
it->second = std::min(it->second, cost);
}
}
}
}
// auto& vec = dp[s][k];
// vec.assign(map.begin(), map.end());
// clear_vec(s, dp[s][k]);
// map.clear();
// for (auto [s, v] : vec) {
// map[s] = v;
// }
}
}
auto& vec = dp[s][k];
vec.assign(map.begin(), map.end());
clear_vec(s, dp[s][k]);
}
{
int i = s;
std::cerr << i << " ";
// std::cerr << i << " ";
// for (int j = 0; j < LG; j++) {
// std::cerr << dp[i][j].size() << " \n"[j == LG - 1];
// }
std::cerr.flush();
}
}
int64_t total_sum = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < LG; j++) {
total_sum += dp[i][j].size();
}
}
for (int i = 1; i <= n; i++) {
int s = 0;
for (int j = 0; j < LG; j++) {
for (auto [a, b] : dp[i][j]) {
s += std::min<int>(20, a.size()) + 4;
}
}
std::cerr << s << "\n";
}
std::cerr << "total: " << total_sum << std::endl;
std::cerr << shit[0] << " " << shit[1] << "\n";
for (auto& vec : inputs) {
int m = vec.size();
int64_t ans = 1e18;
std::sort(vec.begin(), vec.end());
for (int k = 0; k < LG; k++) {
for (auto [vc2, ct] : dp[m][k]) {
std::vector<char> vc;
for (int i = 0; i < vc2.size(); i++) {
vc.insert(vc.end(), vc2[i], i);
}
int64_t res = 0;
res += ct;
for (int i = 0; i < m; i++) {
res += vec.rbegin()[i] * int64_t(vc[i]);
}
ans = std::min(ans, res);
}
}
std::cout << ans << "\n";
}
return 0;
}
#include <iostream>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
constexpr int N = 105;
constexpr int LG = 41;
int64_t shit[10];
std::vector<std::pair<std::string, int64_t>> dp[N][LG];
void clear_vec(int s, std::vector<std::pair<std::string, int64_t>>& vec) {
if (vec.empty()) {
return;
}
std::sort(vec.begin(), vec.end());
std::list<std::remove_reference_t<decltype(vec[0])>> list(vec.rbegin(), vec.rend());
std::vector<int> prf1;
auto check = [&](const auto& it, const auto& it2) {
if (it.second <= it2.second) {
// return true;
bool fk = true;
int sz = std::min(it.first.size(), it2.first.size());
for (int t = 0, sm2 = 0; t < sz; t++) {
// sm1 += it.first[t];
sm2 += it2.first[t];
fk &= prf1[t] >= sm2;
}
return fk;
}
return false;
};
// for (int k : std::array{10, 10}) {
for (int k : std::array{20, 100, 200}) {
for (auto it = std::prev(list.end());; it--) {
int dlt = 0;
prf1.assign(it->first.size(), 0);
for (int t = 0, s = 0; t < it->first.size(); t++) {
s += it->first[t];
prf1[t] = s;
}
for (auto it2 = std::next(it); dlt < k && it2 != list.end(); it2++) {
if (check(*it, *it2)) {
it2--;
list.erase(std::next(it2));
} else {
dlt++;
}
}
if (it == list.begin()) {
break;
}
}
}
vec.assign(list.begin(), list.end());
vec.shrink_to_fit();
}
void clear_vec2(int s, std::vector<std::pair<std::string, int64_t>>& vec) {
std::sort(vec.begin(), vec.end());
// std::sort(vec.rbegin(), vec.rend());
auto check = [&](const auto& it, const auto& it2) {
if (it.second <= it2.second) {
bool fk = true;
int sz = std::min(it.first.size(), it2.first.size());
for (int t = 0, sm1 = 0, sm2 = 0; t < sz; t++) {
sm1 += it.first[t];
sm2 += it2.first[t];
fk &= sm1 >= sm2;
}
return fk;
}
return false;
};
std::remove_reference_t<decltype(vec)> vec2;
while (vec.size() > 0) {
auto p = vec.back();
vec.pop_back();
while (vec.size() > 0) {
if (check(p, vec.back())) {
vec.pop_back();
continue;
}
if (vec.size() > 1 && check(p, vec.rbegin()[1])) {
vec.erase(vec.end() - 2);
continue;
}
if (vec.size() > 2 && check(p, vec.rbegin()[2])) {
vec.erase(vec.end() - 3);
continue;
}
break;
}
vec2.push_back(p);
}
vec.swap(vec2);
vec.shrink_to_fit();
}
int32_t main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int n = 0;
int t;
std::cin >> t;
std::vector<std::vector<int>> inputs(t);
for (auto& vec : inputs) {
int k;
std::cin >> k;
vec.resize(k);
for (auto& i : vec) {
std::cin >> i;
}
n = std::max(n, k);
}
dp[1][0] = {{std::string(1, 1), 0}};
for (int s = 2; s <= n; s++) {
std::vector<int> ord(s - 1);
std::iota(ord.begin(), ord.end(), 1);
std::sort(ord.begin(), ord.end(), [&](int a, int b) { return abs(a - s / 2) < abs(b - s / 2); });
for (int k = 0; k < LG; k++) {
static std::unordered_map<std::string, int64_t> map;
// static __gnu_pbds::cc_hash_table<std::string, int64_t> map;
map.clear();
for (int k1 = 0; k1 < LG; k1++) {
for (int k2 = 0; k2 < LG; k2++) {
if (k != std::max(k1, k2) + 1) {
continue;
}
for (int s1 : ord) {
int s2 = s - s1;
if (dp[s1][k1].empty() || dp[s2][k2].empty()) {
continue;
}
if (k >= LG) {
continue;
}
for (auto [v1, c1] : dp[s1][k1]) {
for (auto [v2, c2] : dp[s2][k2]) {
v2.resize(std::max(v2.size(), v1.size() + 1));
for (int i = 0; i < v1.size(); i++) {
v2[i + 1] += v1[i];
}
int64_t cost = c1 + c2 + ((1LL << k1) - 1) + ((1LL << k2) - 1);
auto [it, suc] = map.insert({v2, cost});
if (!suc) {
it->second = std::min(it->second, cost);
}
}
}
}
// auto& vec = dp[s][k];
// vec.assign(map.begin(), map.end());
// clear_vec(s, dp[s][k]);
// map.clear();
// for (auto [s, v] : vec) {
// map[s] = v;
// }
}
}
auto& vec = dp[s][k];
vec.assign(map.begin(), map.end());
clear_vec(s, dp[s][k]);
}
{
int i = s;
std::cerr << i << " ";
// std::cerr << i << " ";
// for (int j = 0; j < LG; j++) {
// std::cerr << dp[i][j].size() << " \n"[j == LG - 1];
// }
std::cerr.flush();
}
}
int64_t total_sum = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < LG; j++) {
total_sum += dp[i][j].size();
}
}
for (int i = 1; i <= n; i++) {
int s = 0;
for (int j = 0; j < LG; j++) {
for (auto [a, b] : dp[i][j]) {
s += std::min<int>(20, a.size()) + 4;
}
}
std::cerr << s << "\n";
}
std::cerr << "total: " << total_sum << std::endl;
std::cerr << shit[0] << " " << shit[1] << "\n";
for (auto& vec : inputs) {
int m = vec.size();
int64_t ans = 1e18;
std::sort(vec.begin(), vec.end());
for (int k = 0; k < LG; k++) {
for (auto [vc2, ct] : dp[m][k]) {
std::vector<char> vc;
for (int i = 0; i < vc2.size(); i++) {
vc.insert(vc.end(), vc2[i], i);
}
int64_t res = 0;
res += ct;
for (int i = 0; i < m; i++) {
res += vec.rbegin()[i] * int64_t(vc[i]);
}
ans = std::min(ans, res);
}
}
std::cout << ans << "\n";
}
return 0;
}
#include <iostream>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
constexpr int N = 105;
constexpr int LG = 41;
int64_t shit[10];
std::vector<std::pair<std::string, int64_t>> dp[N][LG];
void clear_vec(int s, std::vector<std::pair<std::string, int64_t>>& vec) {
if (vec.empty()) {
return;
}
std::sort(vec.begin(), vec.end());
std::list<std::remove_reference_t<decltype(vec[0])>> list(vec.rbegin(), vec.rend());
std::vector<int> prf1;
auto check = [&](const auto& it, const auto& it2) {
if (it.second <= it2.second) {
// return true;
bool fk = true;
int sz = std::min(it.first.size(), it2.first.size());
for (int t = 0, sm2 = 0; t < sz; t++) {
// sm1 += it.first[t];
sm2 += it2.first[t];
fk &= prf1[t] >= sm2;
}
return fk;
}
return false;
};
// for (int k : std::array{10, 10}) {
for (int k : std::array{20, 100, 200}) {
for (auto it = std::prev(list.end());; it--) {
int dlt = 0;
prf1.assign(it->first.size(), 0);
for (int t = 0, s = 0; t < it->first.size(); t++) {
s += it->first[t];
prf1[t] = s;
}
for (auto it2 = std::next(it); dlt < k && it2 != list.end(); it2++) {
if (check(*it, *it2)) {
it2--;
list.erase(std::next(it2));
} else {
dlt++;
}
}
if (it == list.begin()) {
break;
}
}
}
vec.assign(list.begin(), list.end());
vec.shrink_to_fit();
}
void clear_vec2(int s, std::vector<std::pair<std::string, int64_t>>& vec) {
std::sort(vec.begin(), vec.end());
// std::sort(vec.rbegin(), vec.rend());
auto check = [&](const auto& it, const auto& it2) {
if (it.second <= it2.second) {
bool fk = true;
int sz = std::min(it.first.size(), it2.first.size());
for (int t = 0, sm1 = 0, sm2 = 0; t < sz; t++) {
sm1 += it.first[t];
sm2 += it2.first[t];
fk &= sm1 >= sm2;
}
return fk;
}
return false;
};
std::remove_reference_t<decltype(vec)> vec2;
while (vec.size() > 0) {
auto p = vec.back();
vec.pop_back();
while (vec.size() > 0) {
if (check(p, vec.back())) {
vec.pop_back();
continue;
}
if (vec.size() > 1 && check(p, vec.rbegin()[1])) {
vec.erase(vec.end() - 2);
continue;
}
if (vec.size() > 2 && check(p, vec.rbegin()[2])) {
vec.erase(vec.end() - 3);
continue;
}
break;
}
vec2.push_back(p);
}
vec.swap(vec2);
vec.shrink_to_fit();
}
int32_t main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int n = 0;
int t;
std::cin >> t;
std::vector<std::vector<int>> inputs(t);
for (auto& vec : inputs) {
int k;
std::cin >> k;
vec.resize(k);
for (auto& i : vec) {
std::cin >> i;
}
n = std::max(n, k);
}
dp[1][0] = {{std::string(1, 1), 0}};
for (int s = 2; s <= n; s++) {
std::vector<int> ord(s - 1);
std::iota(ord.begin(), ord.end(), 1);
std::sort(ord.begin(), ord.end(), [&](int a, int b) { return abs(a - s / 2) < abs(b - s / 2); });
for (int k = 0; k < LG; k++) {
static std::unordered_map<std::string, int64_t> map;
// static __gnu_pbds::cc_hash_table<std::string, int64_t> map;
map.clear();
for (int k1 = 0; k1 < LG; k1++) {
for (int k2 = 0; k2 < LG; k2++) {
if (k != std::max(k1, k2) + 1) {
continue;
}
for (int s1 : ord) {
int s2 = s - s1;
if (dp[s1][k1].empty() || dp[s2][k2].empty()) {
continue;
}
if (k >= LG) {
continue;
}
for (auto [v1, c1] : dp[s1][k1]) {
for (auto [v2, c2] : dp[s2][k2]) {
v2.resize(std::max(v2.size(), v1.size() + 1));
for (int i = 0; i < v1.size(); i++) {
v2[i + 1] += v1[i];
}
int64_t cost = c1 + c2 + ((1LL << k1) - 1) + ((1LL << k2) - 1);
auto [it, suc] = map.insert({v2, cost});
if (!suc) {
it->second = std::min(it->second, cost);
}
}
}
}
// auto& vec = dp[s][k];
// vec.assign(map.begin(), map.end());
// clear_vec(s, dp[s][k]);
// map.clear();
// for (auto [s, v] : vec) {
// map[s] = v;
// }
}
}
auto& vec = dp[s][k];
vec.assign(map.begin(), map.end());
clear_vec(s, dp[s][k]);
}
{
int i = s;
std::cerr << i << " ";
// std::cerr << i << " ";
// for (int j = 0; j < LG; j++) {
// std::cerr << dp[i][j].size() << " \n"[j == LG - 1];
// }
std::cerr.flush();
}
}
int64_t total_sum = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < LG; j++) {
total_sum += dp[i][j].size();
}
}
for (int i = 1; i <= n; i++) {
int s = 0;
for (int j = 0; j < LG; j++) {
for (auto [a, b] : dp[i][j]) {
s += std::min<int>(20, a.size()) + 4;
}
}
std::cerr << s << "\n";
}
std::cerr << "total: " << total_sum << std::endl;
std::cerr << shit[0] << " " << shit[1] << "\n";
for (auto& vec : inputs) {
int m = vec.size();
int64_t ans = 1e18;
std::sort(vec.begin(), vec.end());
for (int k = 0; k < LG; k++) {
for (auto [vc2, ct] : dp[m][k]) {
std::vector<char> vc;
for (int i = 0; i < vc2.size(); i++) {
vc.insert(vc.end(), vc2[i], i);
}
int64_t res = 0;
res += ct;
for (int i = 0; i < m; i++) {
res += vec.rbegin()[i] * int64_t(vc[i]);
}
ans = std::min(ans, res);
}
}
std::cout << ans << "\n";
}
return 0;
}
#include <iostream>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
constexpr int N = 105;
constexpr int LG = 41;
int64_t shit[10];
std::vector<std::pair<std::string, int64_t>> dp[N][LG];
void clear_vec(int s, std::vector<std::pair<std::string, int64_t>>& vec) {
if (vec.empty()) {
return;
}
std::sort(vec.begin(), vec.end());
std::list<std::remove_reference_t<decltype(vec[0])>> list(vec.rbegin(), vec.rend());
std::vector<int> prf1;
auto check = [&](const auto& it, const auto& it2) {
if (it.second <= it2.second) {
// return true;
bool fk = true;
int sz = std::min(it.first.size(), it2.first.size());
for (int t = 0, sm2 = 0; t < sz; t++) {
// sm1 += it.first[t];
sm2 += it2.first[t];
fk &= prf1[t] >= sm2;
}
return fk;
}
return false;
};
// for (int k : std::array{10, 10}) {
for (int k : std::array{20, 100, 200}) {
for (auto it = std::prev(list.end());; it--) {
int dlt = 0;
prf1.assign(it->first.size(), 0);
for (int t = 0, s = 0; t < it->first.size(); t++) {
s += it->first[t];
prf1[t] = s;
}
for (auto it2 = std::next(it); dlt < k && it2 != list.end(); it2++) {
if (check(*it, *it2)) {
it2--;
list.erase(std::next(it2));
} else {
dlt++;
}
}
if (it == list.begin()) {
break;
}
}
}
vec.assign(list.begin(), list.end());
vec.shrink_to_fit();
}
void clear_vec2(int s, std::vector<std::pair<std::string, int64_t>>& vec) {
std::sort(vec.begin(), vec.end());
// std::sort(vec.rbegin(), vec.rend());
auto check = [&](const auto& it, const auto& it2) {
if (it.second <= it2.second) {
bool fk = true;
int sz = std::min(it.first.size(), it2.first.size());
for (int t = 0, sm1 = 0, sm2 = 0; t < sz; t++) {
sm1 += it.first[t];
sm2 += it2.first[t];
fk &= sm1 >= sm2;
}
return fk;
}
return false;
};
std::remove_reference_t<decltype(vec)> vec2;
while (vec.size() > 0) {
auto p = vec.back();
vec.pop_back();
while (vec.size() > 0) {
if (check(p, vec.back())) {
vec.pop_back();
continue;
}
if (vec.size() > 1 && check(p, vec.rbegin()[1])) {
vec.erase(vec.end() - 2);
continue;
}
if (vec.size() > 2 && check(p, vec.rbegin()[2])) {
vec.erase(vec.end() - 3);
continue;
}
break;
}
vec2.push_back(p);
}
vec.swap(vec2);
vec.shrink_to_fit();
}
int32_t main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int n = 0;
int t;
std::cin >> t;
std::vector<std::vector<int>> inputs(t);
for (auto& vec : inputs) {
int k;
std::cin >> k;
vec.resize(k);
for (auto& i : vec) {
std::cin >> i;
}
n = std::max(n, k);
}
dp[1][0] = {{std::string(1, 1), 0}};
for (int s = 2; s <= n; s++) {
std::vector<int> ord(s - 1);
std::iota(ord.begin(), ord.end(), 1);
std::sort(ord.begin(), ord.end(), [&](int a, int b) { return abs(a - s / 2) < abs(b - s / 2); });
for (int k = 0; k < LG; k++) {
static std::unordered_map<std::string, int64_t> map;
// static __gnu_pbds::cc_hash_table<std::string, int64_t> map;
map.clear();
for (int k1 = 0; k1 < LG; k1++) {
for (int k2 = 0; k2 < LG; k2++) {
if (k != std::max(k1, k2) + 1) {
continue;
}
for (int s1 : ord) {
int s2 = s - s1;
if (dp[s1][k1].empty() || dp[s2][k2].empty()) {
continue;
}
if (k >= LG) {
continue;
}
for (auto [v1, c1] : dp[s1][k1]) {
for (auto [v2, c2] : dp[s2][k2]) {
v2.resize(std::max(v2.size(), v1.size() + 1));
for (int i = 0; i < v1.size(); i++) {
v2[i + 1] += v1[i];
}
int64_t cost = c1 + c2 + ((1LL << k1) - 1) + ((1LL << k2) - 1);
auto [it, suc] = map.insert({v2, cost});
if (!suc) {
it->second = std::min(it->second, cost);
}
}
}
}
// auto& vec = dp[s][k];
// vec.assign(map.begin(), map.end());
// clear_vec(s, dp[s][k]);
// map.clear();
// for (auto [s, v] : vec) {
// map[s] = v;
// }
}
}
auto& vec = dp[s][k];
vec.assign(map.begin(), map.end());
clear_vec(s, dp[s][k]);
}
{
int i = s;
std::cerr << i << " ";
// std::cerr << i << " ";
// for (int j = 0; j < LG; j++) {
// std::cerr << dp[i][j].size() << " \n"[j == LG - 1];
// }
std::cerr.flush();
}
}
int64_t total_sum = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < LG; j++) {
total_sum += dp[i][j].size();
}
}
for (int i = 1; i <= n; i++) {
int s = 0;
for (int j = 0; j < LG; j++) {
for (auto [a, b] : dp[i][j]) {
s += std::min<int>(20, a.size()) + 4;
}
}
std::cerr << s << "\n";
}
std::cerr << "total: " << total_sum << std::endl;
std::cerr << shit[0] << " " << shit[1] << "\n";
for (auto& vec : inputs) {
int m = vec.size();
int64_t ans = 1e18;
std::sort(vec.begin(), vec.end());
for (int k = 0; k < LG; k++) {
for (auto [vc2, ct] : dp[m][k]) {
std::vector<char> vc;
for (int i = 0; i < vc2.size(); i++) {
vc.insert(vc.end(), vc2[i], i);
}
int64_t res = 0;
res += ct;
for (int i = 0; i < m; i++) {
res += vec.rbegin()[i] * int64_t(vc[i]);
}
ans = std::min(ans, res);
}
}
std::cout << ans << "\n";
}
return 0;
}
#include <iostream>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
constexpr int N = 105;
constexpr int LG = 41;
int64_t shit[10];
std::vector<std::pair<std::string, int64_t>> dp[N][LG];
void clear_vec(int s, std::vector<std::pair<std::string, int64_t>>& vec) {
if (vec.empty()) {
return;
}
std::sort(vec.begin(), vec.end());
std::list<std::remove_reference_t<decltype(vec[0])>> list(vec.rbegin(), vec.rend());
std::vector<int> prf1;
auto check = [&](const auto& it, const auto& it2) {
if (it.second <= it2.second) {
// return true;
bool fk = true;
int sz = std::min(it.first.size(), it2.first.size());
for (int t = 0, sm2 = 0; t < sz; t++) {
// sm1 += it.first[t];
sm2 += it2.first[t];
fk &= prf1[t] >= sm2;
}
return fk;
}
return false;
};
// for (int k : std::array{10, 10}) {
for (int k : std::array{20, 100, 200}) {
for (auto it = std::prev(list.end());; it--) {
int dlt = 0;
prf1.assign(it->first.size(), 0);
for (int t = 0, s = 0; t < it->first.size(); t++) {
s += it->first[t];
prf1[t] = s;
}
for (auto it2 = std::next(it); dlt < k && it2 != list.end(); it2++) {
if (check(*it, *it2)) {
it2--;
list.erase(std::next(it2));
} else {
dlt++;
}
}
if (it == list.begin()) {
break;
}
}
}
vec.assign(list.begin(), list.end());
vec.shrink_to_fit();
}
void clear_vec2(int s, std::vector<std::pair<std::string, int64_t>>& vec) {
std::sort(vec.begin(), vec.end());
// std::sort(vec.rbegin(), vec.rend());
auto check = [&](const auto& it, const auto& it2) {
if (it.second <= it2.second) {
bool fk = true;
int sz = std::min(it.first.size(), it2.first.size());
for (int t = 0, sm1 = 0, sm2 = 0; t < sz; t++) {
sm1 += it.first[t];
sm2 += it2.first[t];
fk &= sm1 >= sm2;
}
return fk;
}
return false;
};
std::remove_reference_t<decltype(vec)> vec2;
while (vec.size() > 0) {
auto p = vec.back();
vec.pop_back();
while (vec.size() > 0) {
if (check(p, vec.back())) {
vec.pop_back();
continue;
}
if (vec.size() > 1 && check(p, vec.rbegin()[1])) {
vec.erase(vec.end() - 2);
continue;
}
if (vec.size() > 2 && check(p, vec.rbegin()[2])) {
vec.erase(vec.end() - 3);
continue;
}
break;
}
vec2.push_back(p);
}
vec.swap(vec2);
vec.shrink_to_fit();
}
int32_t main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int n = 0;
int t;
std::cin >> t;
std::vector<std::vector<int>> inputs(t);
for (auto& vec : inputs) {
int k;
std::cin >> k;
vec.resize(k);
for (auto& i : vec) {
std::cin >> i;
}
n = std::max(n, k);
}
dp[1][0] = {{std::string(1, 1), 0}};
for (int s = 2; s <= n; s++) {
std::vector<int> ord(s - 1);
std::iota(ord.begin(), ord.end(), 1);
std::sort(ord.begin(), ord.end(), [&](int a, int b) { return abs(a - s / 2) < abs(b - s / 2); });
for (int k = 0; k < LG; k++) {
static std::unordered_map<std::string, int64_t> map;
// static __gnu_pbds::cc_hash_table<std::string, int64_t> map;
map.clear();
for (int k1 = 0; k1 < LG; k1++) {
for (int k2 = 0; k2 < LG; k2++) {
if (k != std::max(k1, k2) + 1) {
continue;
}
for (int s1 : ord) {
int s2 = s - s1;
if (dp[s1][k1].empty() || dp[s2][k2].empty()) {
continue;
}
if (k >= LG) {
continue;
}
for (auto [v1, c1] : dp[s1][k1]) {
for (auto [v2, c2] : dp[s2][k2]) {
v2.resize(std::max(v2.size(), v1.size() + 1));
for (int i = 0; i < v1.size(); i++) {
v2[i + 1] += v1[i];
}
int64_t cost = c1 + c2 + ((1LL << k1) - 1) + ((1LL << k2) - 1);
auto [it, suc] = map.insert({v2, cost});
if (!suc) {
it->second = std::min(it->second, cost);
}
}
}
}
// auto& vec = dp[s][k];
// vec.assign(map.begin(), map.end());
// clear_vec(s, dp[s][k]);
// map.clear();
// for (auto [s, v] : vec) {
// map[s] = v;
// }
}
}
auto& vec = dp[s][k];
vec.assign(map.begin(), map.end());
clear_vec(s, dp[s][k]);
}
{
int i = s;
std::cerr << i << " ";
// std::cerr << i << " ";
// for (int j = 0; j < LG; j++) {
// std::cerr << dp[i][j].size() << " \n"[j == LG - 1];
// }
std::cerr.flush();
}
}
int64_t total_sum = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < LG; j++) {
total_sum += dp[i][j].size();
}
}
for (int i = 1; i <= n; i++) {
int s = 0;
for (int j = 0; j < LG; j++) {
for (auto [a, b] : dp[i][j]) {
s += std::min<int>(20, a.size()) + 4;
}
}
std::cerr << s << "\n";
}
std::cerr << "total: " << total_sum << std::endl;
std::cerr << shit[0] << " " << shit[1] << "\n";
for (auto& vec : inputs) {
int m = vec.size();
int64_t ans = 1e18;
std::sort(vec.begin(), vec.end());
for (int k = 0; k < LG; k++) {
for (auto [vc2, ct] : dp[m][k]) {
std::vector<char> vc;
for (int i = 0; i < vc2.size(); i++) {
vc.insert(vc.end(), vc2[i], i);
}
int64_t res = 0;
res += ct;
for (int i = 0; i < m; i++) {
res += vec.rbegin()[i] * int64_t(vc[i]);
}
ans = std::min(ans, res);
}
}
std::cout << ans << "\n";
}
return 0;
}
#include <iostream>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
constexpr int N = 105;
constexpr int LG = 41;
int64_t shit[10];
std::vector<std::pair<std::string, int64_t>> dp[N][LG];
void clear_vec(int s, std::vector<std::pair<std::string, int64_t>>& vec) {
if (vec.empty()) {
return;
}
std::sort(vec.begin(), vec.end());
std::list<std::remove_reference_t<decltype(vec[0])>> list(vec.rbegin(), vec.rend());
std::vector<int> prf1;
auto check = [&](const auto& it, const auto& it2) {
if (it.second <= it2.second) {
// return true;
bool fk = true;
int sz = std::min(it.first.size(), it2.first.size());
for (int t = 0, sm2 = 0; t < sz; t++) {
// sm1 += it.first[t];
sm2 += it2.first[t];
fk &= prf1[t] >= sm2;
}
return fk;
}
return false;
};
// for (int k : std::array{10, 10}) {
for (int k : std::array{20, 100, 200}) {
for (auto it = std::prev(list.end());; it--) {
int dlt = 0;
prf1.assign(it->first.size(), 0);
for (int t = 0, s = 0; t < it->first.size(); t++) {
s += it->first[t];
prf1[t] = s;
}
for (auto it2 = std::next(it); dlt < k && it2 != list.end(); it2++) {
if (check(*it, *it2)) {
it2--;
list.erase(std::next(it2));
} else {
dlt++;
}
}
if (it == list.begin()) {
break;
}
}
}
vec.assign(list.begin(), list.end());
vec.shrink_to_fit();
}
void clear_vec2(int s, std::vector<std::pair<std::string, int64_t>>& vec) {
std::sort(vec.begin(), vec.end());
// std::sort(vec.rbegin(), vec.rend());
auto check = [&](const auto& it, const auto& it2) {
if (it.second <= it2.second) {
bool fk = true;
int sz = std::min(it.first.size(), it2.first.size());
for (int t = 0, sm1 = 0, sm2 = 0; t < sz; t++) {
sm1 += it.first[t];
sm2 += it2.first[t];
fk &= sm1 >= sm2;
}
return fk;
}
return false;
};
std::remove_reference_t<decltype(vec)> vec2;
while (vec.size() > 0) {
auto p = vec.back();
vec.pop_back();
while (vec.size() > 0) {
if (check(p, vec.back())) {
vec.pop_back();
continue;
}
if (vec.size() > 1 && check(p, vec.rbegin()[1])) {
vec.erase(vec.end() - 2);
continue;
}
if (vec.size() > 2 && check(p, vec.rbegin()[2])) {
vec.erase(vec.end() - 3);
continue;
}
break;
}
vec2.push_back(p);
}
vec.swap(vec2);
vec.shrink_to_fit();
}
int32_t main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int n = 0;
int t;
std::cin >> t;
std::vector<std::vector<int>> inputs(t);
for (auto& vec : inputs) {
int k;
std::cin >> k;
vec.resize(k);
for (auto& i : vec) {
std::cin >> i;
}
n = std::max(n, k);
}
dp[1][0] = {{std::string(1, 1), 0}};
for (int s = 2; s <= n; s++) {
std::vector<int> ord(s - 1);
std::iota(ord.begin(), ord.end(), 1);
std::sort(ord.begin(), ord.end(), [&](int a, int b) { return abs(a - s / 2) < abs(b - s / 2); });
for (int k = 0; k < LG; k++) {
static std::unordered_map<std::string, int64_t> map;
// static __gnu_pbds::cc_hash_table<std::string, int64_t> map;
map.clear();
for (int k1 = 0; k1 < LG; k1++) {
for (int k2 = 0; k2 < LG; k2++) {
if (k != std::max(k1, k2) + 1) {
continue;
}
for (int s1 : ord) {
int s2 = s - s1;
if (dp[s1][k1].empty() || dp[s2][k2].empty()) {
continue;
}
if (k >= LG) {
continue;
}
for (auto [v1, c1] : dp[s1][k1]) {
for (auto [v2, c2] : dp[s2][k2]) {
v2.resize(std::max(v2.size(), v1.size() + 1));
for (int i = 0; i < v1.size(); i++) {
v2[i + 1] += v1[i];
}
int64_t cost = c1 + c2 + ((1LL << k1) - 1) + ((1LL << k2) - 1);
auto [it, suc] = map.insert({v2, cost});
if (!suc) {
it->second = std::min(it->second, cost);
}
}
}
}
// auto& vec = dp[s][k];
// vec.assign(map.begin(), map.end());
// clear_vec(s, dp[s][k]);
// map.clear();
// for (auto [s, v] : vec) {
// map[s] = v;
// }
}
}
auto& vec = dp[s][k];
vec.assign(map.begin(), map.end());
clear_vec(s, dp[s][k]);
}
{
int i = s;
std::cerr << i << " ";
// std::cerr << i << " ";
// for (int j = 0; j < LG; j++) {
// std::cerr << dp[i][j].size() << " \n"[j == LG - 1];
// }
std::cerr.flush();
}
}
int64_t total_sum = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < LG; j++) {
total_sum += dp[i][j].size();
}
}
for (int i = 1; i <= n; i++) {
int s = 0;
for (int j = 0; j < LG; j++) {
for (auto [a, b] : dp[i][j]) {
s += std::min<int>(20, a.size()) + 4;
}
}
std::cerr << s << "\n";
}
std::cerr << "total: " << total_sum << std::endl;
std::cerr << shit[0] << " " << shit[1] << "\n";
for (auto& vec : inputs) {
int m = vec.size();
int64_t ans = 1e18;
std::sort(vec.begin(), vec.end());
for (int k = 0; k < LG; k++) {
for (auto [vc2, ct] : dp[m][k]) {
std::vector<char> vc;
for (int i = 0; i < vc2.size(); i++) {
vc.insert(vc.end(), vc2[i], i);
}
int64_t res = 0;
res += ct;
for (int i = 0; i < m; i++) {
res += vec.rbegin()[i] * int64_t(vc[i]);
}
ans = std::min(ans, res);
}
}
std::cout << ans << "\n";
}
return 0;
}
#include <iostream>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
constexpr int N = 105;
constexpr int LG = 41;
int64_t shit[10];
std::vector<std::pair<std::string, int64_t>> dp[N][LG];
void clear_vec(int s, std::vector<std::pair<std::string, int64_t>>& vec) {
if (vec.empty()) {
return;
}
std::sort(vec.begin(), vec.end());
std::list<std::remove_reference_t<decltype(vec[0])>> list(vec.rbegin(), vec.rend());
std::vector<int> prf1;
auto check = [&](const auto& it, const auto& it2) {
if (it.second <= it2.second) {
// return true;
bool fk = true;
int sz = std::min(it.first.size(), it2.first.size());
for (int t = 0, sm2 = 0; t < sz; t++) {
// sm1 += it.first[t];
sm2 += it2.first[t];
fk &= prf1[t] >= sm2;
}
return fk;
}
return false;
};
// for (int k : std::array{10, 10}) {
for (int k : std::array{20, 100, 200}) {
for (auto it = std::prev(list.end());; it--) {
int dlt = 0;
prf1.assign(it->first.size(), 0);
for (int t = 0, s = 0; t < it->first.size(); t++) {
s += it->first[t];
prf1[t] = s;
}
for (auto it2 = std::next(it); dlt < k && it2 != list.end(); it2++) {
if (check(*it, *it2)) {
it2--;
list.erase(std::next(it2));
} else {
dlt++;
}
}
if (it == list.begin()) {
break;
}
}
}
vec.assign(list.begin(), list.end());
vec.shrink_to_fit();
}
void clear_vec2(int s, std::vector<std::pair<std::string, int64_t>>& vec) {
std::sort(vec.begin(), vec.end());
// std::sort(vec.rbegin(), vec.rend());
auto check = [&](const auto& it, const auto& it2) {
if (it.second <= it2.second) {
bool fk = true;
int sz = std::min(it.first.size(), it2.first.size());
for (int t = 0, sm1 = 0, sm2 = 0; t < sz; t++) {
sm1 += it.first[t];
sm2 += it2.first[t];
fk &= sm1 >= sm2;
}
return fk;
}
return false;
};
std::remove_reference_t<decltype(vec)> vec2;
while (vec.size() > 0) {
auto p = vec.back();
vec.pop_back();
while (vec.size() > 0) {
if (check(p, vec.back())) {
vec.pop_back();
continue;
}
if (vec.size() > 1 && check(p, vec.rbegin()[1])) {
vec.erase(vec.end() - 2);
continue;
}
if (vec.size() > 2 && check(p, vec.rbegin()[2])) {
vec.erase(vec.end() - 3);
continue;
}
break;
}
vec2.push_back(p);
}
vec.swap(vec2);
vec.shrink_to_fit();
}
int32_t main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int n = 0;
int t;
std::cin >> t;
std::vector<std::vector<int>> inputs(t);
for (auto& vec : inputs) {
int k;
std::cin >> k;
vec.resize(k);
for (auto& i : vec) {
std::cin >> i;
}
n = std::max(n, k);
}
dp[1][0] = {{std::string(1, 1), 0}};
for (int s = 2; s <= n; s++) {
std::vector<int> ord(s - 1);
std::iota(ord.begin(), ord.end(), 1);
std::sort(ord.begin(), ord.end(), [&](int a, int b) { return abs(a - s / 2) < abs(b - s / 2); });
for (int k = 0; k < LG; k++) {
static std::unordered_map<std::string, int64_t> map;
// static __gnu_pbds::cc_hash_table<std::string, int64_t> map;
map.clear();
for (int k1 = 0; k1 < LG; k1++) {
for (int k2 = 0; k2 < LG; k2++) {
if (k != std::max(k1, k2) + 1) {
continue;
}
for (int s1 : ord) {
int s2 = s - s1;
if (dp[s1][k1].empty() || dp[s2][k2].empty()) {
continue;
}
if (k >= LG) {
continue;
}
for (auto [v1, c1] : dp[s1][k1]) {
for (auto [v2, c2] : dp[s2][k2]) {
v2.resize(std::max(v2.size(), v1.size() + 1));
for (int i = 0; i < v1.size(); i++) {
v2[i + 1] += v1[i];
}
int64_t cost = c1 + c2 + ((1LL << k1) - 1) + ((1LL << k2) - 1);
auto [it, suc] = map.insert({v2, cost});
if (!suc) {
it->second = std::min(it->second, cost);
}
}
}
}
// auto& vec = dp[s][k];
// vec.assign(map.begin(), map.end());
// clear_vec(s, dp[s][k]);
// map.clear();
// for (auto [s, v] : vec) {
// map[s] = v;
// }
}
}
auto& vec = dp[s][k];
vec.assign(map.begin(), map.end());
clear_vec(s, dp[s][k]);
}
{
int i = s;
std::cerr << i << " ";
// std::cerr << i << " ";
// for (int j = 0; j < LG; j++) {
// std::cerr << dp[i][j].size() << " \n"[j == LG - 1];
// }
std::cerr.flush();
}
}
int64_t total_sum = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < LG; j++) {
total_sum += dp[i][j].size();
}
}
for (int i = 1; i <= n; i++) {
int s = 0;
for (int j = 0; j < LG; j++) {
for (auto [a, b] : dp[i][j]) {
s += std::min<int>(20, a.size()) + 4;
}
}
std::cerr << s << "\n";
}
std::cerr << "total: " << total_sum << std::endl;
std::cerr << shit[0] << " " << shit[1] << "\n";
for (auto& vec : inputs) {
int m = vec.size();
int64_t ans = 1e18;
std::sort(vec.begin(), vec.end());
for (int k = 0; k < LG; k++) {
for (auto [vc2, ct] : dp[m][k]) {
std::vector<char> vc;
for (int i = 0; i < vc2.size(); i++) {
vc.insert(vc.end(), vc2[i], i);
}
int64_t res = 0;
res += ct;
for (int i = 0; i < m; i++) {
res += vec.rbegin()[i] * int64_t(vc[i]);
}
ans = std::min(ans, res);
}
}
std::cout << ans << "\n";
}
return 0;
}
#include <iostream>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
constexpr int N = 105;
constexpr int LG = 41;
int64_t shit[10];
std::vector<std::pair<std::string, int64_t>> dp[N][LG];
void clear_vec(int s, std::vector<std::pair<std::string, int64_t>>& vec) {
if (vec.empty()) {
return;
}
std::sort(vec.begin(), vec.end());
std::list<std::remove_reference_t<decltype(vec[0])>> list(vec.rbegin(), vec.rend());
std::vector<int> prf1;
auto check = [&](const auto& it, const auto& it2) {
if (it.second <= it2.second) {
// return true;
bool fk = true;
int sz = std::min(it.first.size(), it2.first.size());
for (int t = 0, sm2 = 0; t < sz; t++) {
// sm1 += it.first[t];
sm2 += it2.first[t];
fk &= prf1[t] >= sm2;
}
return fk;
}
return false;
};
// for (int k : std::array{10, 10}) {
for (int k : std::array{20, 100, 200}) {
for (auto it = std::prev(list.end());; it--) {
int dlt = 0;
prf1.assign(it->first.size(), 0);
for (int t = 0, s = 0; t < it->first.size(); t++) {
s += it->first[t];
prf1[t] = s;
}
for (auto it2 = std::next(it); dlt < k && it2 != list.end(); it2++) {
if (check(*it, *it2)) {
it2--;
list.erase(std::next(it2));
} else {
dlt++;
}
}
if (it == list.begin()) {
break;
}
}
}
vec.assign(list.begin(), list.end());
vec.shrink_to_fit();
}
void clear_vec2(int s, std::vector<std::pair<std::string, int64_t>>& vec) {
std::sort(vec.begin(), vec.end());
// std::sort(vec.rbegin(), vec.rend());
auto check = [&](const auto& it, const auto& it2) {
if (it.second <= it2.second) {
bool fk = true;
int sz = std::min(it.first.size(), it2.first.size());
for (int t = 0, sm1 = 0, sm2 = 0; t < sz; t++) {
sm1 += it.first[t];
sm2 += it2.first[t];
fk &= sm1 >= sm2;
}
return fk;
}
return false;
};
std::remove_reference_t<decltype(vec)> vec2;
while (vec.size() > 0) {
auto p = vec.back();
vec.pop_back();
while (vec.size() > 0) {
if (check(p, vec.back())) {
vec.pop_back();
continue;
}
if (vec.size() > 1 && check(p, vec.rbegin()[1])) {
vec.erase(vec.end() - 2);
continue;
}
if (vec.size() > 2 && check(p, vec.rbegin()[2])) {
vec.erase(vec.end() - 3);
continue;
}
break;
}
vec2.push_back(p);
}
vec.swap(vec2);
vec.shrink_to_fit();
}
int32_t main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int n = 0;
int t;
std::cin >> t;
std::vector<std::vector<int>> inputs(t);
for (auto& vec : inputs) {
int k;
std::cin >> k;
vec.resize(k);
for (auto& i : vec) {
std::cin >> i;
}
n = std::max(n, k);
}
dp[1][0] = {{std::string(1, 1), 0}};
for (int s = 2; s <= n; s++) {
std::vector<int> ord(s - 1);
std::iota(ord.begin(), ord.end(), 1);
std::sort(ord.begin(), ord.end(), [&](int a, int b) { return abs(a - s / 2) < abs(b - s / 2); });
for (int k = 0; k < LG; k++) {
static std::unordered_map<std::string, int64_t> map;
// static __gnu_pbds::cc_hash_table<std::string, int64_t> map;
map.clear();
for (int k1 = 0; k1 < LG; k1++) {
for (int k2 = 0; k2 < LG; k2++) {
if (k != std::max(k1, k2) + 1) {
continue;
}
for (int s1 : ord) {
int s2 = s - s1;
if (dp[s1][k1].empty() || dp[s2][k2].empty()) {
continue;
}
if (k >= LG) {
continue;
}
for (auto [v1, c1] : dp[s1][k1]) {
for (auto [v2, c2] : dp[s2][k2]) {
v2.resize(std::max(v2.size(), v1.size() + 1));
for (int i = 0; i < v1.size(); i++) {
v2[i + 1] += v1[i];
}
int64_t cost = c1 + c2 + ((1LL << k1) - 1) + ((1LL << k2) - 1);
auto [it, suc] = map.insert({v2, cost});
if (!suc) {
it->second = std::min(it->second, cost);
}
}
}
}
// auto& vec = dp[s][k];
// vec.assign(map.begin(), map.end());
// clear_vec(s, dp[s][k]);
// map.clear();
// for (auto [s, v] : vec) {
// map[s] = v;
// }
}
}
auto& vec = dp[s][k];
vec.assign(map.begin(), map.end());
clear_vec(s, dp[s][k]);
}
{
int i = s;
std::cerr << i << " ";
// std::cerr << i << " ";
// for (int j = 0; j < LG; j++) {
// std::cerr << dp[i][j].size() << " \n"[j == LG - 1];
// }
std::cerr.flush();
}
}
int64_t total_sum = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < LG; j++) {
total_sum += dp[i][j].size();
}
}
for (int i = 1; i <= n; i++) {
int s = 0;
for (int j = 0; j < LG; j++) {
for (auto [a, b] : dp[i][j]) {
s += std::min<int>(20, a.size()) + 4;
}
}
std::cerr << s << "\n";
}
std::cerr << "total: " << total_sum << std::endl;
std::cerr << shit[0] << " " << shit[1] << "\n";
for (auto& vec : inputs) {
int m = vec.size();
int64_t ans = 1e18;
std::sort(vec.begin(), vec.end());
for (int k = 0; k < LG; k++) {
for (auto [vc2, ct] : dp[m][k]) {
std::vector<char> vc;
for (int i = 0; i < vc2.size(); i++) {
vc.insert(vc.end(), vc2[i], i);
}
int64_t res = 0;
res += ct;
for (int i = 0; i < m; i++) {
res += vec.rbegin()[i] * int64_t(vc[i]);
}
ans = std::min(ans, res);
}
}
std::cout << ans << "\n";
}
return 0;
}
#include <iostream>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
constexpr int N = 105;
constexpr int LG = 41;
int64_t shit[10];
std::vector<std::pair<std::string, int64_t>> dp[N][LG];
void clear_vec(int s, std::vector<std::pair<std::string, int64_t>>& vec) {
if (vec.empty()) {
return;
}
std::sort(vec.begin(), vec.end());
std::list<std::remove_reference_t<decltype(vec[0])>> list(vec.rbegin(), vec.rend());
std::vector<int> prf1;
auto check = [&](const auto& it, const auto& it2) {
if (it.second <= it2.second) {
// return true;
bool fk = true;
int sz = std::min(it.first.size(), it2.first.size());
for (int t = 0, sm2 = 0; t < sz; t++) {
// sm1 += it.first[t];
sm2 += it2.first[t];
fk &= prf1[t] >= sm2;
}
return fk;
}
return false;
};
// for (int k : std::array{10, 10}) {
for (int k : std::array{20, 100, 200}) {
for (auto it = std::prev(list.end());; it--) {
int dlt = 0;
prf1.assign(it->first.size(), 0);
for (int t = 0, s = 0; t < it->first.size(); t++) {
s += it->first[t];
prf1[t] = s;
}
for (auto it2 = std::next(it); dlt < k && it2 != list.end(); it2++) {
if (check(*it, *it2)) {
it2--;
list.erase(std::next(it2));
} else {
dlt++;
}
}
if (it == list.begin()) {
break;
}
}
}
vec.assign(list.begin(), list.end());
vec.shrink_to_fit();
}
void clear_vec2(int s, std::vector<std::pair<std::string, int64_t>>& vec) {
std::sort(vec.begin(), vec.end());
// std::sort(vec.rbegin(), vec.rend());
auto check = [&](const auto& it, const auto& it2) {
if (it.second <= it2.second) {
bool fk = true;
int sz = std::min(it.first.size(), it2.first.size());
for (int t = 0, sm1 = 0, sm2 = 0; t < sz; t++) {
sm1 += it.first[t];
sm2 += it2.first[t];
fk &= sm1 >= sm2;
}
return fk;
}
return false;
};
std::remove_reference_t<decltype(vec)> vec2;
while (vec.size() > 0) {
auto p = vec.back();
vec.pop_back();
while (vec.size() > 0) {
if (check(p, vec.back())) {
vec.pop_back();
continue;
}
if (vec.size() > 1 && check(p, vec.rbegin()[1])) {
vec.erase(vec.end() - 2);
continue;
}
if (vec.size() > 2 && check(p, vec.rbegin()[2])) {
vec.erase(vec.end() - 3);
continue;
}
break;
}
vec2.push_back(p);
}
vec.swap(vec2);
vec.shrink_to_fit();
}
int32_t main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int n = 0;
int t;
std::cin >> t;
std::vector<std::vector<int>> inputs(t);
for (auto& vec : inputs) {
int k;
std::cin >> k;
vec.resize(k);
for (auto& i : vec) {
std::cin >> i;
}
n = std::max(n, k);
}
dp[1][0] = {{std::string(1, 1), 0}};
for (int s = 2; s <= n; s++) {
std::vector<int> ord(s - 1);
std::iota(ord.begin(), ord.end(), 1);
std::sort(ord.begin(), ord.end(), [&](int a, int b) { return abs(a - s / 2) < abs(b - s / 2); });
for (int k = 0; k < LG; k++) {
static std::unordered_map<std::string, int64_t> map;
// static __gnu_pbds::cc_hash_table<std::string, int64_t> map;
map.clear();
for (int k1 = 0; k1 < LG; k1++) {
for (int k2 = 0; k2 < LG; k2++) {
if (k != std::max(k1, k2) + 1) {
continue;
}
for (int s1 : ord) {
int s2 = s - s1;
if (dp[s1][k1].empty() || dp[s2][k2].empty()) {
continue;
}
if (k >= LG) {
continue;
}
for (auto [v1, c1] : dp[s1][k1]) {
for (auto [v2, c2] : dp[s2][k2]) {
v2.resize(std::max(v2.size(), v1.size() + 1));
for (int i = 0; i < v1.size(); i++) {
v2[i + 1] += v1[i];
}
int64_t cost = c1 + c2 + ((1LL << k1) - 1) + ((1LL << k2) - 1);
auto [it, suc] = map.insert({v2, cost});
if (!suc) {
it->second = std::min(it->second, cost);
}
}
}
}
// auto& vec = dp[s][k];
// vec.assign(map.begin(), map.end());
// clear_vec(s, dp[s][k]);
// map.clear();
// for (auto [s, v] : vec) {
// map[s] = v;
// }
}
}
auto& vec = dp[s][k];
vec.assign(map.begin(), map.end());
clear_vec(s, dp[s][k]);
}
{
int i = s;
std::cerr << i << " ";
// std::cerr << i << " ";
// for (int j = 0; j < LG; j++) {
// std::cerr << dp[i][j].size() << " \n"[j == LG - 1];
// }
std::cerr.flush();
}
}
int64_t total_sum = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < LG; j++) {
total_sum += dp[i][j].size();
}
}
for (int i = 1; i <= n; i++) {
int s = 0;
for (int j = 0; j < LG; j++) {
for (auto [a, b] : dp[i][j]) {
s += std::min<int>(20, a.size()) + 4;
}
}
std::cerr << s << "\n";
}
std::cerr << "total: " << total_sum << std::endl;
std::cerr << shit[0] << " " << shit[1] << "\n";
for (auto& vec : inputs) {
int m = vec.size();
int64_t ans = 1e18;
std::sort(vec.begin(), vec.end());
for (int k = 0; k < LG; k++) {
for (auto [vc2, ct] : dp[m][k]) {
std::vector<char> vc;
for (int i = 0; i < vc2.size(); i++) {
vc.insert(vc.end(), vc2[i], i);
}
int64_t res = 0;
res += ct;
for (int i = 0; i < m; i++) {
res += vec.rbegin()[i] * int64_t(vc[i]);
}
ans = std::min(ans, res);
}
}
std::cout << ans << "\n";
}
return 0;
}
#include <iostream>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
constexpr int N = 105;
constexpr int LG = 41;
int64_t shit[10];
std::vector<std::pair<std::string, int64_t>> dp[N][LG];
void clear_vec(int s, std::vector<std::pair<std::string, int64_t>>& vec) {
if (vec.empty()) {
return;
}
std::sort(vec.begin(), vec.end());
std::list<std::remove_reference_t<decltype(vec[0])>> list(vec.rbegin(), vec.rend());
std::vector<int> prf1;
auto check = [&](const auto& it, const auto& it2) {
if (it.second <= it2.second) {
// return true;
bool fk = true;
int sz = std::min(it.first.size(), it2.first.size());
for (int t = 0, sm2 = 0; t < sz; t++) {
// sm1 += it.first[t];
sm2 += it2.first[t];
fk &= prf1[t] >= sm2;
}
return fk;
}
return false;
};
// for (int k : std::array{10, 10}) {
for (int k : std::array{20, 100, 200}) {
for (auto it = std::prev(list.end());; it--) {
int dlt = 0;
prf1.assign(it->first.size(), 0);
for (int t = 0, s = 0; t < it->first.size(); t++) {
s += it->first[t];
prf1[t] = s;
}
for (auto it2 = std::next(it); dlt < k && it2 != list.end(); it2++) {
if (check(*it, *it2)) {
it2--;
list.erase(std::next(it2));
} else {
dlt++;
}
}
if (it == list.begin()) {
break;
}
}
}
vec.assign(list.begin(), list.end());
vec.shrink_to_fit();
}
void clear_vec2(int s, std::vector<std::pair<std::string, int64_t>>& vec) {
std::sort(vec.begin(), vec.end());
// std::sort(vec.rbegin(), vec.rend());
auto check = [&](const auto& it, const auto& it2) {
if (it.second <= it2.second) {
bool fk = true;
int sz = std::min(it.first.size(), it2.first.size());
for (int t = 0, sm1 = 0, sm2 = 0; t < sz; t++) {
sm1 += it.first[t];
sm2 += it2.first[t];
fk &= sm1 >= sm2;
}
return fk;
}
return false;
};
std::remove_reference_t<decltype(vec)> vec2;
while (vec.size() > 0) {
auto p = vec.back();
vec.pop_back();
while (vec.size() > 0) {
if (check(p, vec.back())) {
vec.pop_back();
continue;
}
if (vec.size() > 1 && check(p, vec.rbegin()[1])) {
vec.erase(vec.end() - 2);
continue;
}
if (vec.size() > 2 && check(p, vec.rbegin()[2])) {
vec.erase(vec.end() - 3);
continue;
}
break;
}
vec2.push_back(p);
}
vec.swap(vec2);
vec.shrink_to_fit();
}
int32_t main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int n = 0;
int t;
std::cin >> t;
std::vector<std::vector<int>> inputs(t);
for (auto& vec : inputs) {
int k;
std::cin >> k;
vec.resize(k);
for (auto& i : vec) {
std::cin >> i;
}
n = std::max(n, k);
}
dp[1][0] = {{std::string(1, 1), 0}};
for (int s = 2; s <= n; s++) {
std::vector<int> ord(s - 1);
std::iota(ord.begin(), ord.end(), 1);
std::sort(ord.begin(), ord.end(), [&](int a, int b) { return abs(a - s / 2) < abs(b - s / 2); });
for (int k = 0; k < LG; k++) {
static std::unordered_map<std::string, int64_t> map;
// static __gnu_pbds::cc_hash_table<std::string, int64_t> map;
map.clear();
for (int k1 = 0; k1 < LG; k1++) {
for (int k2 = 0; k2 < LG; k2++) {
if (k != std::max(k1, k2) + 1) {
continue;
}
for (int s1 : ord) {
int s2 = s - s1;
if (dp[s1][k1].empty() || dp[s2][k2].empty()) {
continue;
}
if (k >= LG) {
continue;
}
for (auto [v1, c1] : dp[s1][k1]) {
for (auto [v2, c2] : dp[s2][k2]) {
v2.resize(std::max(v2.size(), v1.size() + 1));
for (int i = 0; i < v1.size(); i++) {
v2[i + 1] += v1[i];
}
int64_t cost = c1 + c2 + ((1LL << k1) - 1) + ((1LL << k2) - 1);
auto [it, suc] = map.insert({v2, cost});
if (!suc) {
it->second = std::min(it->second, cost);
}
}
}
}
// auto& vec = dp[s][k];
// vec.assign(map.begin(), map.end());
// clear_vec(s, dp[s][k]);
// map.clear();
// for (auto [s, v] : vec) {
// map[s] = v;
// }
}
}
auto& vec = dp[s][k];
vec.assign(map.begin(), map.end());
clear_vec(s, dp[s][k]);
}
{
int i = s;
std::cerr << i << " ";
// std::cerr << i << " ";
// for (int j = 0; j < LG; j++) {
// std::cerr << dp[i][j].size() << " \n"[j == LG - 1];
// }
std::cerr.flush();
}
}
int64_t total_sum = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < LG; j++) {
total_sum += dp[i][j].size();
}
}
for (int i = 1; i <= n; i++) {
int s = 0;
for (int j = 0; j < LG; j++) {
for (auto [a, b] : dp[i][j]) {
s += std::min<int>(20, a.size()) + 4;
}
}
std::cerr << s << "\n";
}
std::cerr << "total: " << total_sum << std::endl;
std::cerr << shit[0] << " " << shit[1] << "\n";
for (auto& vec : inputs) {
int m = vec.size();
int64_t ans = 1e18;
std::sort(vec.begin(), vec.end());
for (int k = 0; k < LG; k++) {
for (auto [vc2, ct] : dp[m][k]) {
std::vector<char> vc;
for (int i = 0; i < vc2.size(); i++) {
vc.insert(vc.end(), vc2[i], i);
}
int64_t res = 0;
res += ct;
for (int i = 0; i < m; i++) {
res += vec.rbegin()[i] * int64_t(vc[i]);
}
ans = std::min(ans, res);
}
}
std::cout << ans << "\n";
}
return 0;
}
#include <iostream>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
constexpr int N = 105;
constexpr int LG = 41;
int64_t shit[10];
std::vector<std::pair<std::string, int64_t>> dp[N][LG];
void clear_vec(int s, std::vector<std::pair<std::string, int64_t>>& vec) {
if (vec.empty()) {
return;
}
std::sort(vec.begin(), vec.end());
std::list<std::remove_reference_t<decltype(vec[0])>> list(vec.rbegin(), vec.rend());
std::vector<int> prf1;
auto check = [&](const auto& it, const auto& it2) {
if (it.second <= it2.second) {
// return true;
bool fk = true;
int sz = std::min(it.first.size(), it2.first.size());
for (int t = 0, sm2 = 0; t < sz; t++) {
// sm1 += it.first[t];
sm2 += it2.first[t];
fk &= prf1[t] >= sm2;
}
return fk;
}
return false;
};
// for (int k : std::array{10, 10}) {
for (int k : std::array{20, 100, 200}) {
for (auto it = std::prev(list.end());; it--) {
int dlt = 0;
prf1.assign(it->first.size(), 0);
for (int t = 0, s = 0; t < it->first.size(); t++) {
s += it->first[t];
prf1[t] = s;
}
for (auto it2 = std::next(it); dlt < k && it2 != list.end(); it2++) {
if (check(*it, *it2)) {
it2--;
list.erase(std::next(it2));
} else {
dlt++;
}
}
if (it == list.begin()) {
break;
}
}
}
vec.assign(list.begin(), list.end());
vec.shrink_to_fit();
}
void clear_vec2(int s, std::vector<std::pair<std::string, int64_t>>& vec) {
std::sort(vec.begin(), vec.end());
// std::sort(vec.rbegin(), vec.rend());
auto check = [&](const auto& it, const auto& it2) {
if (it.second <= it2.second) {
bool fk = true;
int sz = std::min(it.first.size(), it2.first.size());
for (int t = 0, sm1 = 0, sm2 = 0; t < sz; t++) {
sm1 += it.first[t];
sm2 += it2.first[t];
fk &= sm1 >= sm2;
}
return fk;
}
return false;
};
std::remove_reference_t<decltype(vec)> vec2;
while (vec.size() > 0) {
auto p = vec.back();
vec.pop_back();
while (vec.size() > 0) {
if (check(p, vec.back())) {
vec.pop_back();
continue;
}
if (vec.size() > 1 && check(p, vec.rbegin()[1])) {
vec.erase(vec.end() - 2);
continue;
}
if (vec.size() > 2 && check(p, vec.rbegin()[2])) {
vec.erase(vec.end() - 3);
continue;
}
break;
}
vec2.push_back(p);
}
vec.swap(vec2);
vec.shrink_to_fit();
}
int32_t main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int n = 0;
int t;
std::cin >> t;
std::vector<std::vector<int>> inputs(t);
for (auto& vec : inputs) {
int k;
std::cin >> k;
vec.resize(k);
for (auto& i : vec) {
std::cin >> i;
}
n = std::max(n, k);
}
dp[1][0] = {{std::string(1, 1), 0}};
for (int s = 2; s <= n; s++) {
std::vector<int> ord(s - 1);
std::iota(ord.begin(), ord.end(), 1);
std::sort(ord.begin(), ord.end(), [&](int a, int b) { return abs(a - s / 2) < abs(b - s / 2); });
for (int k = 0; k < LG; k++) {
static std::unordered_map<std::string, int64_t> map;
// static __gnu_pbds::cc_hash_table<std::string, int64_t> map;
map.clear();
for (int k1 = 0; k1 < LG; k1++) {
for (int k2 = 0; k2 < LG; k2++) {
if (k != std::max(k1, k2) + 1) {
continue;
}
for (int s1 : ord) {
int s2 = s - s1;
if (dp[s1][k1].empty() || dp[s2][k2].empty()) {
continue;
}
if (k >= LG) {
continue;
}
for (auto [v1, c1] : dp[s1][k1]) {
for (auto [v2, c2] : dp[s2][k2]) {
v2.resize(std::max(v2.size(), v1.size() + 1));
for (int i = 0; i < v1.size(); i++) {
v2[i + 1] += v1[i];
}
int64_t cost = c1 + c2 + ((1LL << k1) - 1) + ((1LL << k2) - 1);
auto [it, suc] = map.insert({v2, cost});
if (!suc) {
it->second = std::min(it->second, cost);
}
}
}
}
// auto& vec = dp[s][k];
// vec.assign(map.begin(), map.end());
// clear_vec(s, dp[s][k]);
// map.clear();
// for (auto [s, v] : vec) {
// map[s] = v;
// }
}
}
auto& vec = dp[s][k];
vec.assign(map.begin(), map.end());
clear_vec(s, dp[s][k]);
}
{
int i = s;
std::cerr << i << " ";
// std::cerr << i << " ";
// for (int j = 0; j < LG; j++) {
// std::cerr << dp[i][j].size() << " \n"[j == LG - 1];
// }
std::cerr.flush();
}
}
int64_t total_sum = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < LG; j++) {
total_sum += dp[i][j].size();
}
}
for (int i = 1; i <= n; i++) {
int s = 0;
for (int j = 0; j < LG; j++) {
for (auto [a, b] : dp[i][j]) {
s += std::min<int>(20, a.size()) + 4;
}
}
std::cerr << s << "\n";
}
std::cerr << "total: " << total_sum << std::endl;
std::cerr << shit[0] << " " << shit[1] << "\n";
for (auto& vec : inputs) {
int m = vec.size();
int64_t ans = 1e18;
std::sort(vec.begin(), vec.end());
for (int k = 0; k < LG; k++) {
for (auto [vc2, ct] : dp[m][k]) {
std::vector<char> vc;
for (int i = 0; i < vc2.size(); i++) {
vc.insert(vc.end(), vc2[i], i);
}
int64_t res = 0;
res += ct;
for (int i = 0; i < m; i++) {
res += vec.rbegin()[i] * int64_t(vc[i]);
}
ans = std::min(ans, res);
}
}
std::cout << ans << "\n";
}
return 0;
}
#include <iostream>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
constexpr int N = 105;
constexpr int LG = 41;
int64_t shit[10];
std::vector<std::pair<std::string, int64_t>> dp[N][LG];
void clear_vec(int s, std::vector<std::pair<std::string, int64_t>>& vec) {
if (vec.empty()) {
return;
}
std::sort(vec.begin(), vec.end());
std::list<std::remove_reference_t<decltype(vec[0])>> list(vec.rbegin(), vec.rend());
std::vector<int> prf1;
auto check = [&](const auto& it, const auto& it2) {
if (it.second <= it2.second) {
// return true;
bool fk = true;
int sz = std::min(it.first.size(), it2.first.size());
for (int t = 0, sm2 = 0; t < sz; t++) {
// sm1 += it.first[t];
sm2 += it2.first[t];
fk &= prf1[t] >= sm2;
}
return fk;
}
return false;
};
// for (int k : std::array{10, 10}) {
for (int k : std::array{20, 100, 200}) {
for (auto it = std::prev(list.end());; it--) {
int dlt = 0;
prf1.assign(it->first.size(), 0);
for (int t = 0, s = 0; t < it->first.size(); t++) {
s += it->first[t];
prf1[t] = s;
}
for (auto it2 = std::next(it); dlt < k && it2 != list.end(); it2++) {
if (check(*it, *it2)) {
it2--;
list.erase(std::next(it2));
} else {
dlt++;
}
}
if (it == list.begin()) {
break;
}
}
}
vec.assign(list.begin(), list.end());
vec.shrink_to_fit();
}
void clear_vec2(int s, std::vector<std::pair<std::string, int64_t>>& vec) {
std::sort(vec.begin(), vec.end());
// std::sort(vec.rbegin(), vec.rend());
auto check = [&](const auto& it, const auto& it2) {
if (it.second <= it2.second) {
bool fk = true;
int sz = std::min(it.first.size(), it2.first.size());
for (int t = 0, sm1 = 0, sm2 = 0; t < sz; t++) {
sm1 += it.first[t];
sm2 += it2.first[t];
fk &= sm1 >= sm2;
}
return fk;
}
return false;
};
std::remove_reference_t<decltype(vec)> vec2;
while (vec.size() > 0) {
auto p = vec.back();
vec.pop_back();
while (vec.size() > 0) {
if (check(p, vec.back())) {
vec.pop_back();
continue;
}
if (vec.size() > 1 && check(p, vec.rbegin()[1])) {
vec.erase(vec.end() - 2);
continue;
}
if (vec.size() > 2 && check(p, vec.rbegin()[2])) {
vec.erase(vec.end() - 3);
continue;
}
break;
}
vec2.push_back(p);
}
vec.swap(vec2);
vec.shrink_to_fit();
}
int32_t main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int n = 0;
int t;
std::cin >> t;
std::vector<std::vector<int>> inputs(t);
for (auto& vec : inputs) {
int k;
std::cin >> k;
vec.resize(k);
for (auto& i : vec) {
std::cin >> i;
}
n = std::max(n, k);
}
dp[1][0] = {{std::string(1, 1), 0}};
for (int s = 2; s <= n; s++) {
std::vector<int> ord(s - 1);
std::iota(ord.begin(), ord.end(), 1);
std::sort(ord.begin(), ord.end(), [&](int a, int b) { return abs(a - s / 2) < abs(b - s / 2); });
for (int k = 0; k < LG; k++) {
static std::unordered_map<std::string, int64_t> map;
// static __gnu_pbds::cc_hash_table<std::string, int64_t> map;
map.clear();
for (int k1 = 0; k1 < LG; k1++) {
for (int k2 = 0; k2 < LG; k2++) {
if (k != std::max(k1, k2) + 1) {
continue;
}
for (int s1 : ord) {
int s2 = s - s1;
if (dp[s1][k1].empty() || dp[s2][k2].empty()) {
continue;
}
if (k >= LG) {
continue;
}
for (auto [v1, c1] : dp[s1][k1]) {
for (auto [v2, c2] : dp[s2][k2]) {
v2.resize(std::max(v2.size(), v1.size() + 1));
for (int i = 0; i < v1.size(); i++) {
v2[i + 1] += v1[i];
}
int64_t cost = c1 + c2 + ((1LL << k1) - 1) + ((1LL << k2) - 1);
auto [it, suc] = map.insert({v2, cost});
if (!suc) {
it->second = std::min(it->second, cost);
}
}
}
}
// auto& vec = dp[s][k];
// vec.assign(map.begin(), map.end());
// clear_vec(s, dp[s][k]);
// map.clear();
// for (auto [s, v] : vec) {
// map[s] = v;
// }
}
}
auto& vec = dp[s][k];
vec.assign(map.begin(), map.end());
clear_vec(s, dp[s][k]);
}
{
int i = s;
std::cerr << i << " ";
// std::cerr << i << " ";
// for (int j = 0; j < LG; j++) {
// std::cerr << dp[i][j].size() << " \n"[j == LG - 1];
// }
std::cerr.flush();
}
}
int64_t total_sum = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < LG; j++) {
total_sum += dp[i][j].size();
}
}
for (int i = 1; i <= n; i++) {
int s = 0;
for (int j = 0; j < LG; j++) {
for (auto [a, b] : dp[i][j]) {
s += std::min<int>(20, a.size()) + 4;
}
}
std::cerr << s << "\n";
}
std::cerr << "total: " << total_sum << std::endl;
std::cerr << shit[0] << " " << shit[1] << "\n";
for (auto& vec : inputs) {
int m = vec.size();
int64_t ans = 1e18;
std::sort(vec.begin(), vec.end());
for (int k = 0; k < LG; k++) {
for (auto [vc2, ct] : dp[m][k]) {
std::vector<char> vc;
for (int i = 0; i < vc2.size(); i++) {
vc.insert(vc.end(), vc2[i], i);
}
int64_t res = 0;
res += ct;
for (int i = 0; i < m; i++) {
res += vec.rbegin()[i] * int64_t(vc[i]);
}
ans = std::min(ans, res);
}
}
std::cout << ans << "\n";
}
return 0;
}