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];
}
vector<int> cant(n + m, -1); //0 - right, 1 - down
set<pair<db, int>, greater<>> st;
set<int> rows, columns;
vector<db> last(n + m);
auto update = [&](int i) {
st.erase({last[i], i});
if (i < n) {
auto it = rows.upper_bound(i);
if (it != rows.end()) {
int j = *it;
st.emplace(last[i] = db(a[j] - a[i]) / (j - i), i);
}
} else {
i -= n;
auto it = columns.upper_bound(i);
if (it != columns.end()) {
int j = *it;
st.emplace(last[i + n] = db(b[j] - b[i]) / (j - i), i + n);
}
}
};
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 + m; ++i) {
update(i);
}
while (!st.empty() && rows.size() > 1 && columns.size() > 1) {
auto [delta, i] = *st.begin();
st.erase(st.begin());
if (i < n && !rows.count(i) || i >= n && !columns.count(i - n)) {
continue;
}
if (i >= n) {
cant[i] = 1;
auto it = columns.erase(columns.find(i - n));
if (it != columns.begin()) {
update(*prev(it) + n);
}
} else {
cant[i] = 0;
auto it = rows.erase(rows.find(i));
if (it != rows.begin()) {
update(*prev(it));
}
}
}
// cant[n - 1] = cant[n + m - 1] = -1;
// cant[n - 1] = cant[n + m - 1] = cant[0] = cant[n] = 0;
// for (int i = 0; i < n; ++i) {
// cout << cant[i] << " ";
// }
//
// cout << endl;
//
// for (int j = 0; j < m; ++j) {
// cout << cant[n + j] << " ";
// }
//
// cout << endl;
map<pair<int, int>, ll> saved;
constexpr ll inf = 3e18;
auto solve = [&](auto self, int x, int y) -> ll {
if (y >= m || x >= n) {
return inf;
} else if (x == n - 1 && y == m - 1) {
return 0;
}
if (saved.count({x, y})) {
return saved[{x, y}];
}
ll ans = inf;
if (x == 0 && y == 0) {
ans = min(self(self, x + 1, y) + b[y], self(self, x, y + 1) + a[x]);
}
if (y == m - 1) {
ans = min(ans, 1LL * b[y] * (n - x - 1));
}
if (x == n - 1) {
ans = min(ans, 1LL * a[x] * (m - y - 1));
}
if (cant[x] == -1) {
ans = min(ans, self(self, x + 1, y) + b[y]);
} else {
ans = min(ans, self(self, x, y + 1) + a[x]);
}
if (x < n - 1 && y < m - 1) {
if (last[x] < last[y + n]) {
ans = min(ans, self(self, x, y + 1) + a[x]);
} else {
ans = min(ans, self(self, x + 1, y) + b[y]);
}
}
return saved[{x, y}] = ans;
};
cout << solve(solve, 0, 0) << '\n';
return 0;
}
Compilation message (stderr)
kyoto.cpp: In function 'int main()':
kyoto.cpp:71:19: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
71 | if (i < n && !rows.count(i) || i >= n && !columns.count(i - n)) {
| ~~~~~~^~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |