Submission #705798

#	Time	Username	Problem	Language	Result	Execution time	Memory
705798		piOOE	Sightseeing in Kyoto (JOI22_kyoto)	C++17	0 / 100	0 ms	212 KiB

kyoto

#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)) {
      |             ~~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 30
• Subtask 3: 0 / 60