题解 | #真爱粉Tk（三）#

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

using namespace std;

long long count_25_subsequence_in_string(const string& s) {
    long long count_2 = 0;
    long long count_25 = 0;
    for (char c : s) {
        if (c == '2') {
            count_2++;
        } else if (c == '5') {
            count_25 += count_2;
        }
    }
    return count_25;
}

// Global arrays for precomputation (using 1-based indexing for convenience)
vector<long long> c2;
vector<long long> c5;
vector<long long> c25_internal;
vector<long long> S_c2;
vector<long long> S_c5;
vector<long long> S_c25_internal;
vector<long long> S_D; // Prefix sum of c2[p] * S_c5[p]

// Function to calculate the number of "25" subsequences in the concatenated string of a[start...end]
long long get_25_subsequence_count(int start, int end) {
    if (start > end) {
        return 0;
    }

    // Internal "25" subsequences
    long long internal_25s = S_c25_internal[end] - S_c25_internal[start - 1];

    if (start == end) {
        return internal_25s;
    }

    // Cross-number "25" subsequences
    // Sum_{p=start}^{end-1} c2[p] * (Sum_{q=p+1}^end c5[q])
    // Sum_{q=p+1}^end c5[q] = S_c5[end] - S_c5[p]

    // Term 1: Sum_{p=start}^{end-1} c2[p] * S_c5[end]
    long long sum_c2_start_to_end_minus_1 = S_c2[end - 1] - S_c2[start - 1];
    long long term1 = S_c5[end] * sum_c2_start_to_end_minus_1;

    // Term 2: Sum_{p=start}^{end-1} c2[p] * S_c5[p]
    long long sum_D_start_to_end_minus_1 = S_D[end - 1] - S_D[start - 1];

    long long cross_25s = term1 - sum_D_start_to_end_minus_1;

    return internal_25s + cross_25s;
}

// Check if it's possible to partition into <= k subarrays with max "25" subsequence count <= X
bool can(long long X, int n, int k) {
    int num_partitions = 0;
    int current_pos = 1;

    while (current_pos <= n) {
        num_partitions++;
        if (num_partitions > k) {
            return false;
        }

        int low = current_pos, high = n, best_end_pos = current_pos - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (get_25_subsequence_count(current_pos, mid) <= X) {
                best_end_pos = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        if (best_end_pos < current_pos) {
             return false; // Cannot even form a single valid partition
        }

        current_pos = best_end_pos + 1;
    }

    return true; // Successfully partitioned into <= k segments
}

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

    int n;
    long long k;
    cin >> n >> k;

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

    // Precomputation
    c2.resize(n + 1, 0);
    c5.resize(n + 1, 0);
    c25_internal.resize(n + 1, 0);
    S_c2.resize(n + 1, 0);
    S_c5.resize(n + 1, 0);
    S_c25_internal.resize(n + 1, 0);
    S_D.resize(n + 1, 0);

    for (int i = 1; i <= n; ++i) {
        string s = to_string(a[i]);
        for (char c : s) {
            if (c == '2') c2[i]++;
            else if (c == '5') c5[i]++;
        }
        c25_internal[i] = count_25_subsequence_in_string(s);

        S_c2[i] = S_c2[i - 1] + c2[i];
        S_c5[i] = S_c5[i - 1] + c5[i];
        S_c25_internal[i] = S_c25_internal[i - 1] + c25_internal[i];
    }

    for (int i = 1; i <= n; ++i) {
         S_D[i] = S_D[i-1] + c2[i] * S_c5[i];
    }


    // Binary search for the answer
    long long low = 0, high = get_25_subsequence_count(1, n);
    long long ans = high;

    while (low <= high) {
        long long mid = low + (high - low) / 2;
        if (can(mid, n, k)) {
            ans = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    cout << ans << endl;

    return 0;
}