Submission #1243452

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243452		Aviansh	Sightseeing in Kyoto (JOI22_kyoto)	C++20	10 / 100	2097 ms	101160 KiB

kyoto

#include <bits/stdc++.h>

using namespace std;

#define int long long

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int h,w;
    cin >> h >> w;
    int A[h],B[w];
    for(int i = 0;i<h;i++){
        cin >> A[i];
    }
    for(int i = 0;i<w;i++){
        cin >> B[i];
    }
    priority_queue<array<int,3>,vector<array<int,3>>,greater<array<int,3>>>pq;
    pq.push({0,0,0});
    map<array<int,2>,int>dist;
    while(!pq.empty()){
        array<int,3>a=pq.top();
        pq.pop();
        array<int,2> pt = {a[1],a[2]};
        if(dist.find(pt)!=dist.end()){
            if(dist[pt]<=a[0]){
                continue;
            }
        }
        dist[pt]=a[0];
        if(pt[0]<h-1){
            //can be incd
            pq.push({a[0]+B[pt[1]],pt[0]+1,pt[1]});
        }
        if(pt[1]<w-1){
            pq.push({a[0]+A[pt[0]],pt[0],pt[1]+1});
        }
        if(pt[0]==h-1&&pt[1]==w-1){
            cout << a[0] << "\n";
            return 0;
        }
    }
    return 0;
}

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