Submission #851321

#	Time	Username	Problem	Language	Result	Execution time	Memory
851321		niter	Sightseeing in Kyoto (JOI22_kyoto)	C++14	10 / 100	400 ms	243904 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)(5e6) + 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 << 11) + j; }
inline int get_i(int x){ return x >> 11; }
inline int get_j(int x){ return x & 2047; }
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();
    assert(max(n, m) <= 2000);

    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 / 10
• Subtask 2: 0 / 30
• Subtask 3: 0 / 60