OI XXXIII - pro (Firmowka)

// https://sio2.mimuw.edu.pl/c/oi33-2/p/

// Prognoza pogody

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    vector<int> T(n);
    for (int i = 0; i < n; ++i) {
        cin >> T[i];
    }

    vector<int> P(m);
    for (int i = 0; i < m; ++i) {
        cin >> P[i];
    }

    vector<int> current_costs(m);

    int min_mismatches = m + 1;
    for (int shift = 0; shift < m; ++shift) {
        int mismatches = 0;
        for (int k = 0; k < m; ++k) {
            int p_val = P[(shift + k) % m];
            if (p_val != T[k]) {
                mismatches++;
            }
        }
        current_costs[shift] = mismatches;
        if (mismatches < min_mismatches) {
            min_mismatches = mismatches;
        }
    }

    vector<int> next_costs(m);

    for (int i = 0; i < n - m; ++i) {
        for (int j = 0; j < m; ++j) {
            int leaving_comparison_matches = (P[j] == T[i]);
            int entering_comparison_matches = (P[j] == T[i + m]);

            int current_val = current_costs[j];

            if (!leaving_comparison_matches) current_val--;
            if (!entering_comparison_matches) current_val++;

            next_costs[(j + 1) % m] = current_val;
        }

        current_costs = next_costs;

        for (int val : current_costs) {
            if (val < min_mismatches) {
                min_mismatches = val;
            }
        }
    }

    cout << min_mismatches << endl;

    return 0;
}