This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> a(n), b(m);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
for (int j = 0; j < m; ++j) {
cin >> b[j];
}
set<tuple<db, int, int>, greater<>> st;
set<int> rows, columns;
vector<int> last(n + m);
int iter = 0;
for (int i = 0; i < n; ++i) {
rows.insert(rows.end(), i);
}
for (int i = 0; i < m; ++i) {
columns.insert(columns.end(), i);
}
for (int i = 0; i < n - 1; ++i) {
st.emplace(a[i + 1] - a[i], i, 0);
}
for (int i = n; i < n + m - 1; ++i) {
st.emplace(b[i + 1 - n] - b[i - n], i, 0);
}
vector<int> when(n + m, -1);
while (!st.empty()) {
auto [delta, i, iteration] = *st.begin();
st.erase(st.begin());
if (last[i] != iteration) {
continue;
}
when[i] = ++iter;
if (i >= n) {
auto it = columns.erase(columns.find(i - n));
if (it != columns.begin()) {
int j = *it, p = *prev(it);
st.emplace(-db(b[j] - b[p]) / (j - p), p + n, last[p + n] = iter);
}
} else {
auto it = rows.erase(rows.find(i));
if (it != rows.begin()) {
int j = *it, p = *prev(it);
st.emplace(-db(a[j] - a[p]) / (j - p), p, last[p] = iter);
}
}
}
int x = 0, y = 0;
ll ans = 0;
while (x < n - 1 || y < m - 1) {
if (x < n - 1 && (y == m - 1 || when[x] > when[y + n])) {
ans += b[y];
x += 1;
} else {
ans += a[x];
y += 1;
}
}
cout << ans << endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |