Submission #548155

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

kyoto

#include <bits/stdc++.h>
#define pb push_back
using namespace std;

using ll = long long;

int h, w;
vector<int> a, b;
vector<int> ca, cb;
void load() {
    cin >> h >> w;
    ca.pb(1), cb.pb(1);
    for (int i = 0; i < h; ++i) {
        int na;
        cin >> na;
        while (a.size() >= 2 && a[a.size() - 2] <= a.back() && na <= a.back()) {
            a.pop_back();
            ca[ca.size() - 2] += ca.back();
            ca.pop_back();
        }
        a.push_back(na);
        ca.pb(1);
    }
    for (int i = 0; i < w; ++i) {
        int na;
        cin >> na;
        while (b.size() >= 2 && b[b.size() - 2] <= b.back() && na <= b.back()) {
            b.pop_back();
            cb[cb.size() - 2] += cb.back();
            cb.pop_back();
        }
        b.push_back(na);
        cb.pb(1);
    }
    h = size(a);
    w = size(b);
}

ll inf = 1ll << 58;

void slowSolve() {
    int dh = h + 10;
    int dw = w + 10;
    ll dp[dh][dw];
    for (int i = 0; i < dh; ++i) {
        for (int j = 0; j < dw; ++j) dp[i][j] = inf;
    }
    dp[1][1] = 0;

    for (int i = 1; i <= h; ++i) {
        for (int j = 1; j <= w; ++j) {
            dp[i][j] = min({dp[i][j], dp[i-1][j] + 1ll * ca[i - 1] * b[j-1], dp[i][j-1] + 1ll * cb[j - 1] * a[i-1]});
        }
    }
    cout << dp[h][w] << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    load();
    slowSolve();

    return 0;
}

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