Submission #705803

#TimeUsernameProblemLanguageResultExecution timeMemory
705803piOOESightseeing in Kyoto (JOI22_kyoto)C++17
0 / 100
1 ms852 KiB
#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 == 0 || i == n) { // cout << "delta " << i << ": " << delta << endl; // } 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, last[p] = 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 + n, last[p + n] = iter); } } } // for (int i = 0; i < n; ++i) cout << when[i] << " "; // cout << endl; // // for (int j = 0; j < m; ++j) cout << when[n + j] << " "; // cout << endl; int x = 0, y = 0; ll ans = 0; while (x < n - 1 || y < m - 1) { // cout << x << " " << y << endl; 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...