提出 #68554275

---

ソースコード 拡げる

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

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

    int N, M, L;
    cin >> N >> M >> L;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    vector<vector<int>> groups(L);
    for (int i = 0; i < N; ++i) {
        groups[i % L].push_back(A[i]);
    }

    vector<int> dp(M, INT_MAX);
    dp[0] = 0;

    for (int r = 0; r < L; ++r) {
        vector<int>& arr = groups[r];
        if (arr.empty()) continue;
        sort(arr.begin(), arr.end());
        int n = arr.size();
        long long total_sum = 0;
        for (int num : arr) {
            total_sum += num;
        }

        vector<long long> cost_x(M);
        for (int x = 0; x < M; ++x) {
            int idx = upper_bound(arr.begin(), arr.end(), x) - arr.begin();
            long long count_le = idx;
            cost_x[x] = (long long)x * n - total_sum + (long long)M * (n - count_le);
        }

        vector<int> new_dp(M, INT_MAX);
        for (int s = 0; s < M; ++s) {
            if (dp[s] == INT_MAX) continue;
            for (int x = 0; x < M; ++x) {
                int new_s = (s + x) % M;
                long long new_cost = (long long)dp[s] + cost_x[x];
                if (new_cost < new_dp[new_s]) {
                    new_dp[new_s] = new_cost;
                }
            }
        }
        dp = move(new_dp);
    }

    cout << dp[0] << endl;
    return 0;
}

提出情報

ジャッジ結果