Submission #56624631

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()


int main() {
    cin.tie(0)->sync_with_stdio(false);

    int n, m;
    cin >> n >> m;

    vector<ll> a(n), b(n);
    for (ll &i : a)
        cin >> i;
    for (ll &i : b)
        cin >> i;

    if (m == 2) {
        cout << (a == b ? 0 : -1) << '\n';
        return 0;
    }

    vector<ll> c(n);
    c[0] = b[0];
    for (int i = 1; i < n; i++) {
        ll d = (b[i] - b[i - 1] + m) % m;

        if (a[i] > a[i - 1])
            c[i] = c[i - 1] + d;
        else
            c[i] = c[i - 1] - (m - d);
    }

    vector<ll> d(n);
    for (int i = 0; i < n; i++)
        d[i] = c[i] - a[i];

    auto check = [&](ll x) {
        ll cost = 0;
        for (int i = 0; i < n; i++)
            cost += abs((c[i] - x * m) - a[i]);
        return cost;
    };

    sort(all(d));

    ll ans = 1e18;
    for (int i = max(n / 2 - 5, 0); i <= min(n / 2 + 5, n - 1); i++) {
        ll f = d[i] / m;
        for (int j = -10; j <= 10; j++)
            ans = min(ans, check(f + j));
    }

    cout << ans << '\n';

    return 0;
}

Submission Info

Judge Result