oj.uz

Submission #851312

# Submission time Handle Problem Language Result Execution time Memory
851312 2023-09-19T14:22:02 Z niter Sightseeing in Kyoto (JOI22_kyoto) C++14
10 / 100
 2000 ms 1048576 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 = 16777216+10;
ll dp[mxn];
int a_in[100005], b_in[100005];
vector<ll> a, b;
vector<ll> mul_a, mul_b;
const ll INF = 4e18;
vector<pair<int, ll>> E[mxn];

inline int hsh(int i, int j){ return (i << 12) + j; }
inline int get_i(int x){ return x >> 12; }
inline int get_j(int x){ return x & 4095; }
void solve(){
    int n, m; cin >> n >> m;
    loop(i,0,n){
        cin >> a_in[i];
    }
    loop(j,0,m){
        cin >> b_in[j];
    }
    a.pb(a_in[0]);
    int now_mul = 1;
    loop(i,1,n-1){
        if(a_in[i] >= a_in[i-1] && a_in[i] >= a_in[i+1]){
            a_in[i] = a_in[i-1];
            now_mul++;
        }
        else{
            a.pb(a_in[i]);
            mul_b.pb(now_mul);
            now_mul = 1;
        }
    }
    a.pb(a_in[n-1]);
    mul_b.pb(now_mul);
    n = a.size();

    now_mul = 1;
    b.pb(b_in[0]);
    loop(i,1,m-1){
        if(b_in[i] >= b_in[i-1] && b_in[i] >= b_in[i+1]){
            b_in[i] = b_in[i-1];
            now_mul++;
        }
        else{
            b.pb(b_in[i]);
            mul_a.pb(now_mul);
            now_mul = 1;
        }
    }
    b.pb(b_in[m-1]);
    mul_a.pb(now_mul);
    m = b.size();

    loop(i,0,n){
        loop(j,0,m){
            dp[hsh(i, j)] = INF;
        }
    }
    loop(i,0,n){
        loop(j,0,m-1){
            E[hsh(i, j)].pb({hsh(i, j+1), a[i] * mul_a[j]});
        }
    }
    loop(j,0,m){
        loop(i,0,n-1){
            E[hsh(i, j)].pb({hsh(i+1, j), b[j] * mul_b[i]});
        }
    }
    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 191 ms 396644 KB Output is correct
2 Correct 82 ms 396516 KB Output is correct
3 Correct 83 ms 396532 KB Output is correct
4 Correct 88 ms 397656 KB Output is correct
5 Correct 83 ms 404800 KB Output is correct
6 Correct 84 ms 403100 KB Output is correct
7 Correct 85 ms 400796 KB Output is correct
8 Correct 85 ms 396652 KB Output is correct
9 Correct 229 ms 431576 KB Output is correct
10 Correct 236 ms 428396 KB Output is correct
11 Correct 218 ms 431444 KB Output is correct
12 Correct 202 ms 430984 KB Output is correct
13 Correct 566 ms 478052 KB Output is correct
14 Correct 198 ms 431188 KB Output is correct
15 Correct 197 ms 430564 KB Output is correct
16 Correct 563 ms 477892 KB Output is correct
17 Correct 84 ms 396624 KB Output is correct
18 Correct 85 ms 396552 KB Output is correct
19 Correct 81 ms 396412 KB Output is correct
20 Correct 86 ms 396724 KB Output is correct
21 Correct 82 ms 396652 KB Output is correct
22 Correct 82 ms 396644 KB Output is correct
23 Correct 82 ms 396628 KB Output is correct
24 Correct 84 ms 396560 KB Output is correct
25 Correct 82 ms 396564 KB Output is correct
26 Correct 83 ms 396628 KB Output is correct
27 Correct 81 ms 396484 KB Output is correct
28 Correct 82 ms 396624 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 396648 KB Output is correct
2 Correct 82 ms 396532 KB Output is correct
3 Correct 180 ms 420176 KB Output is correct
4 Execution timed out 3038 ms 1048576 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 396644 KB Output is correct
2 Correct 82 ms 396516 KB Output is correct
3 Correct 83 ms 396532 KB Output is correct
4 Correct 88 ms 397656 KB Output is correct
5 Correct 83 ms 404800 KB Output is correct
6 Correct 84 ms 403100 KB Output is correct
7 Correct 85 ms 400796 KB Output is correct
8 Correct 85 ms 396652 KB Output is correct
9 Correct 229 ms 431576 KB Output is correct
10 Correct 236 ms 428396 KB Output is correct
11 Correct 218 ms 431444 KB Output is correct
12 Correct 202 ms 430984 KB Output is correct
13 Correct 566 ms 478052 KB Output is correct
14 Correct 198 ms 431188 KB Output is correct
15 Correct 197 ms 430564 KB Output is correct
16 Correct 563 ms 477892 KB Output is correct
17 Correct 84 ms 396624 KB Output is correct
18 Correct 85 ms 396552 KB Output is correct
19 Correct 81 ms 396412 KB Output is correct
20 Correct 86 ms 396724 KB Output is correct
21 Correct 82 ms 396652 KB Output is correct
22 Correct 82 ms 396644 KB Output is correct
23 Correct 82 ms 396628 KB Output is correct
24 Correct 84 ms 396560 KB Output is correct
25 Correct 82 ms 396564 KB Output is correct
26 Correct 83 ms 396628 KB Output is correct
27 Correct 81 ms 396484 KB Output is correct
28 Correct 82 ms 396624 KB Output is correct
29 Correct 84 ms 396648 KB Output is correct
30 Correct 82 ms 396532 KB Output is correct
31 Correct 180 ms 420176 KB Output is correct
32 Execution timed out 3038 ms 1048576 KB Time limit exceeded
33 Halted 0 ms 0 KB -