Submission #850367

#	Time	Username	Problem	Language	Result	Execution time	Memory
850367		niter	Sightseeing in Kyoto (JOI22_kyoto)	C++14	0 / 100	31 ms	64084 KiB

kyoto

#include <bits/stdc++.h>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define pii pair<int,int>
#define pb push_back
#define ins insert
#define ff first
#define ss second
#define opa(x) cout << #x << " = " << x << ", ";
#define op(x) cout << #x << " = " << x << endl;
#define ops(x) cout << x;
#define entr cout << endl;
#define spac cout << ' ';
#define all(x) (x).begin(), (x).end()
#define STL(x) cout << #x << " : "; for(auto &qwe:x) cout << qwe << ' '; cout << endl;
#define arr(x, n) cout << #x << " : "; loop(qwe,0,n) cout << x[qwe] << ' '; cout << endl;
#define deb1 cout << "deb1" << endl;
#define deb2 cout << "deb2" << endl;
#define deb3 cout << "deb3" << endl;
#define deb4 cout << "deb4" << endl;
#define deb5 cout << "deb5" << endl;
using namespace std;
typedef long long ll;

const int mxn = (int)(1e6) + 10;
ll dp[mxn];
int a[1005], b[1005];
const ll INF = 1e18;
vector<pii> E[mxn];

inline int hsh(int i, int j){ return (i << 10) + j; }
inline int get_i(int x){ return x >> 10; }
inline int get_j(int x){ return x & 1023; }
void solve(){
    int n, m; cin >> n >> m;
    assert(n <= 1000);
    assert(m <= 1000);
    loop(i,0,n){
        loop(j,0,m){
            dp[hsh(i, j)] = INF;
        }
    }
    loop(i,0,n){
        int tmp;
        cin >> tmp;
        a[i] = tmp;
        loop(j,0,m-1){
            E[hsh(i, j)].pb({hsh(i, j+1), tmp});
        }
    }
    loop(j,0,m){
        int tmp;
        cin >> tmp;
        b[j] = tmp;
        loop(i,0,n-1){
            E[hsh(i, j)].pb({hsh(i+1, j), tmp});
        }
    }
    dp[0] = 0;
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    pq.push({0, 0});
    while(!pq.empty()){
        ll dis = pq.top().ff;
        int now = pq.top().ss;
//        opa(dis) op(now);
        pq.pop();
        if(dis != dp[now]) continue;
        for(auto &i:E[now]){
            ll nxt_dis = dis + i.ss;
            int nxt = i.ff;
            if(dp[nxt] > nxt_dis){
                dp[nxt] = nxt_dis;
                pq.push({nxt_dis, nxt});
            }
        }
    }
    cout << dp[hsh(n-1, m-1)] << '\n';
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
//    freopen("test_input.txt", "r", stdin);
    int t = 1;
    while(t--){
        solve();
    }
}

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