oj.uz

Submission #850369

# Submission time Handle Problem Language Result Execution time Memory
850369 2023-09-16T12:51:52 Z niter Sightseeing in Kyoto (JOI22_kyoto) C++14
10 / 100
 349 ms 65988 KB 
#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 = 1024000;
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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25176 KB Output is correct
2 Correct 5 ms 25176 KB Output is correct
3 Correct 5 ms 25180 KB Output is correct
4 Correct 13 ms 26972 KB Output is correct
5 Correct 6 ms 29272 KB Output is correct
6 Correct 6 ms 27224 KB Output is correct
7 Correct 6 ms 27224 KB Output is correct
8 Correct 5 ms 25180 KB Output is correct
9 Correct 349 ms 65988 KB Output is correct
10 Correct 342 ms 65988 KB Output is correct
11 Correct 236 ms 64056 KB Output is correct
12 Correct 235 ms 64280 KB Output is correct
13 Correct 231 ms 63824 KB Output is correct
14 Correct 221 ms 63824 KB Output is correct
15 Correct 226 ms 63824 KB Output is correct
16 Correct 233 ms 63832 KB Output is correct
17 Correct 154 ms 63824 KB Output is correct
18 Correct 6 ms 25180 KB Output is correct
19 Correct 6 ms 25180 KB Output is correct
20 Correct 5 ms 25176 KB Output is correct
21 Correct 5 ms 25176 KB Output is correct
22 Correct 5 ms 25176 KB Output is correct
23 Correct 6 ms 25180 KB Output is correct
24 Correct 5 ms 25176 KB Output is correct
25 Correct 6 ms 25176 KB Output is correct
26 Correct 5 ms 25180 KB Output is correct
27 Correct 5 ms 25176 KB Output is correct
28 Correct 5 ms 25176 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25176 KB Output is correct
2 Correct 5 ms 25176 KB Output is correct
3 Runtime error 22 ms 50768 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25176 KB Output is correct
2 Correct 5 ms 25176 KB Output is correct
3 Correct 5 ms 25180 KB Output is correct
4 Correct 13 ms 26972 KB Output is correct
5 Correct 6 ms 29272 KB Output is correct
6 Correct 6 ms 27224 KB Output is correct
7 Correct 6 ms 27224 KB Output is correct
8 Correct 5 ms 25180 KB Output is correct
9 Correct 349 ms 65988 KB Output is correct
10 Correct 342 ms 65988 KB Output is correct
11 Correct 236 ms 64056 KB Output is correct
12 Correct 235 ms 64280 KB Output is correct
13 Correct 231 ms 63824 KB Output is correct
14 Correct 221 ms 63824 KB Output is correct
15 Correct 226 ms 63824 KB Output is correct
16 Correct 233 ms 63832 KB Output is correct
17 Correct 154 ms 63824 KB Output is correct
18 Correct 6 ms 25180 KB Output is correct
19 Correct 6 ms 25180 KB Output is correct
20 Correct 5 ms 25176 KB Output is correct
21 Correct 5 ms 25176 KB Output is correct
22 Correct 5 ms 25176 KB Output is correct
23 Correct 6 ms 25180 KB Output is correct
24 Correct 5 ms 25176 KB Output is correct
25 Correct 6 ms 25176 KB Output is correct
26 Correct 5 ms 25180 KB Output is correct
27 Correct 5 ms 25176 KB Output is correct
28 Correct 5 ms 25176 KB Output is correct
29 Correct 5 ms 25176 KB Output is correct
30 Correct 5 ms 25176 KB Output is correct
31 Runtime error 22 ms 50768 KB Execution killed with signal 6
32 Halted 0 ms 0 KB -