Submission #870686

#	Time	Username	Problem	Language	Result	Execution time	Memory
870686		EJIC_B_KEDAX	Sightseeing in Kyoto (JOI22_kyoto)	C++17	40 / 100	458 ms	1048576 KiB

kyoto

#ifdef LOCAL
    #define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>

#ifndef LOCAL
    // #pragma GCC optimize("O3")
    // #pragma GCC optimize("Ofast")
    // #pragma GCC optimize("unroll-loops")
    // #pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt")
#endif
using namespace std;
using ll = long long;
using ld = long double;
#define x first
#define y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()



mt19937_64 mt(time(0));

void solve();
void init();

int32_t main() {
#ifndef LOCAL
    cin.tie(nullptr)->sync_with_stdio(false);
#else
    freopen("input.txt", "r", stdin);
#endif
    init();
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}

void init() {}

void solve() {
    int h, w;
    cin >> h >> w;
    vector<pair<ll, ll>> a1(h), b1(w), a, b;
    for (int i = 0; i < h; i++) {
        cin >> a1[i].x;
        a1[i].y = 1;
    }
    for (int i = 0; i < w; i++) {
        cin >> b1[i].x;
        b1[i].y = 1;
    }
    for (int i = 0; i < h; i++) {
        while (a.size() >= 3) {
            auto ff = a.back();
            a.pop_back();
            if (!(a1[i].x <= ff.x && a.back().x <= ff.x)) {
                a.push_back(ff);
                break;
            } else {
                a.back().y += ff.y;
            }
        }
        a.push_back(a1[i]);
    }
    for (int i = 0; i < w; i++) {
        while (b.size() >= 3) {
            auto ff = b.back();
            b.pop_back();
            if (!(b1[i].x <= ff.x && b.back().x <= ff.x)) {
                b.push_back(ff);
                break;
            } else {
                b.back().y += ff.y;
            }
        }
        b.push_back(b1[i]);
    }
    h = a.size();
    w = b.size();
    // cout << h << ' ' << w << '\n';
    vector<vector<ll>> dp(h + 1, vector<ll>(w + 1, INT64_MAX));
    // for (auto i : a) {
    //     cout << i.x << ' ' << i.y << '\n';
    // }
    // for (auto i : b) {
    //     cout << i.x << ' ' << i.y << '\n';
    // }
    dp[0][0] = 0;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            // cout << dp[i][j] << ' ';
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + b[j].x * a[i].y);
            dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + a[i].x * b[j].y);
        }
        // cout << '\n';
    }
    cout << dp[h - 1][w - 1] << '\n';
}

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