oj.uz

Submission #705793

# Submission time Handle Problem Language Result Execution time Memory
705793 2023-03-05T09:39:05 Z piOOE Sightseeing in Kyoto (JOI22_kyoto) C++17
10 / 100
 2000 ms 146512 KB 
#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;
        }

//        cout << delta << " " << i << endl;


        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 (cant[y + n] != -1) {
            ans = min(ans, self(self, x + 1, y) + b[y]);
        }

        if (cant[x] != -1) {
            ans = min(ans, self(self, x, y + 1) + a[x]);
        }

        assert(cant[x] != -1 || cant[y + n] != -1);

        return saved[{x, y}] = ans;
    };

    cout << solve(solve, 0, 0) << '\n';

    return 0;
}

Compilation message

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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 316 KB Output is correct
4 Correct 28 ms 3796 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 316 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 800 ms 63184 KB Output is correct
10 Correct 784 ms 63312 KB Output is correct
11 Correct 773 ms 63276 KB Output is correct
12 Correct 791 ms 63292 KB Output is correct
13 Correct 805 ms 63184 KB Output is correct
14 Correct 761 ms 63144 KB Output is correct
15 Correct 778 ms 63248 KB Output is correct
16 Correct 791 ms 63136 KB Output is correct
17 Correct 327 ms 63360 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 316 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 1 ms 320 KB Output is correct
26 Correct 0 ms 212 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 250 ms 25068 KB Output is correct
4 Execution timed out 2083 ms 146512 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 316 KB Output is correct
4 Correct 28 ms 3796 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 316 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 800 ms 63184 KB Output is correct
10 Correct 784 ms 63312 KB Output is correct
11 Correct 773 ms 63276 KB Output is correct
12 Correct 791 ms 63292 KB Output is correct
13 Correct 805 ms 63184 KB Output is correct
14 Correct 761 ms 63144 KB Output is correct
15 Correct 778 ms 63248 KB Output is correct
16 Correct 791 ms 63136 KB Output is correct
17 Correct 327 ms 63360 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 316 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 1 ms 320 KB Output is correct
26 Correct 0 ms 212 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Correct 1 ms 212 KB Output is correct
29 Correct 1 ms 320 KB Output is correct
30 Correct 0 ms 212 KB Output is correct
31 Correct 250 ms 25068 KB Output is correct
32 Execution timed out 2083 ms 146512 KB Time limit exceeded
33 Halted 0 ms 0 KB -