oj.uz

Submission #870682

# Submission time Handle Problem Language Result Execution time Memory
870682 2023-11-08T19:57:15 Z EJIC_B_KEDAX Sightseeing in Kyoto (JOI22_kyoto) C++17
0 / 100
 518 ms 1048576 KB 
#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<int, int>> 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++) {
        if (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);
            } else {
                a.back().y += ff.y;
            }
        }
        a.push_back(a1[i]);
    }
    for (int i = 0; i < w; i++) {
        if (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);
            } 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 344 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 2768 KB Output is correct
4 Runtime error 518 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 344 KB Output isn't correct
4 Halted 0 ms 0 KB -