Submission #836034

#	Time	Username	Problem	Language	Result	Execution time	Memory
836034		josanneo22	Sightseeing in Kyoto (JOI22_kyoto)	C++17	10 / 100	589 ms	1048576 KiB

kyoto

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ld long double
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define ar array

const int inf = 1e18;
void solve() {
    int h, w; cin >> h >> w;
    vector<int> ch(h), cv(w);
    for (int i = 0; i < h; i++) cin >> ch[i];
    for (int i = 0; i < w; i++) cin >> cv[i];
    using node = pair<int, pair<int, int>>;
    vector<vector<int>> dis(h, vector<int>(w,inf));
    priority_queue<node, vector<node>, greater<node>> pq;
    pq.push(mp(0, mp(0, 0)));
    while (pq.size()) {
        node p = pq.top(); pq.pop();
        int x = p.second.first, y = p.second.second, pp = p.first;
        if (dis[x][y] <= pp) continue;
        dis[x][y] = pp;
        if (x + 1 < h) pq.push(mp(pp + cv[y], mp(x + 1, y)));
        if (y + 1 < w) pq.push(mp(pp + ch[x], mp(x, y + 1)));
    }
    cout << dis[h - 1][w - 1] << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    solve();
}

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