Submission #964947

#	Time	Username	Problem	Language	Result	Execution time	Memory
964947		406	Sightseeing in Kyoto (JOI22_kyoto)	C++17	0 / 100	1 ms	2396 KiB

kyoto

#include <bits/stdc++.h>
#define int long long
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)

using namespace std;
using ar = array<int, 2>;

const int64_t INF = 1ll << 60;
const int N = 1e5 + 5;

int n, m, a[N], b[N], suf[N];
bool marka[N], markb[N];

void OK(int a[], int sz, bool mk[]) {
        suf[sz - 1] = a[sz - 1];
        for (int i = sz - 2; i >= 0; --i) 
                suf[i] = min(suf[i + 1], a[i]);
        int mn = a[0];
        FOR(i, 1, sz - 1) {
                if (a[i] >= mn && a[i] >= suf[i + 1])
                        mk[i] = true;
                mn = min(mn, a[i]);
        }
}

int solve(vector<int> a, vector<int> b, vector<int> X, vector<int> Y) {
        /*
        for (auto x: a) cout << x << ' ';
        cout << endl;
        for (auto y: b) cout << y << ' ';
        cout << endl;
        cout << "HERE" << endl;
        */
        int sum = a[0] * (Y.back() - Y[0]) + b[0] * (X.back() - X[0]), n = a.size(), m = b.size();
        for (int x = 0, y = 0; x != n - 1 && y != m - 1; ) {
                int costy = (b[y + 1] - b[y]) * (X.back() - X[x]);
                int costx = (a[x + 1] - a[x]) * (Y.back() - Y[y]);
                //cout << costx << ' ' << costy << endl;
                if (costx <= costy) ++x;
                else ++y;
                sum += min(costx, costy);
        }
        return sum;
}

signed main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr); 
        cin >> n >> m;
        FOR(i, 0, n) cin >> a[i];
        FOR(j, 0, m) cin >> b[j];
        OK(a, n, marka);
        OK(b, m, markb);
        vector<int> A, B, X, Y;
        int mna = min_element(a, a + n) - a, mnb = min_element(b, b + m) - b, sum = 0;
        FOR(i, 0, mna + 1) if (!marka[i]) A.push_back(a[i]), X.push_back(mna - i);
        FOR(i, 0, mnb + 1) if (!markb[i]) B.push_back(b[i]), Y.push_back(mnb - i);
        reverse(A.begin(), A.end());
        reverse(B.begin(), B.end());
        reverse(X.begin(), X.end());
        reverse(Y.begin(), Y.end());

        sum += solve(A, B, X, Y);
        A.clear(), B.clear(), X.clear(), Y.clear();

        FOR(i, mna, n) if (!marka[i]) A.push_back(a[i]), X.push_back(i - mna);
        FOR(i, mnb, m) if (!markb[i]) B.push_back(b[i]), Y.push_back(i - mnb);
        sum += solve(A, B, X, Y);

        cout << sum << '\n';
        return 0;
}

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