Colorful Eggs

2 secs 1024 MB

dyktr_06

問題

提出

テストケース

解説

卵の色ごとに累積和をとっておくと、区間にある色の卵がいくつあるかを $O(1)$ で判定することができます。
よって、この問題を全体で $O(NM)$ で解くことができ、十分に高速です。

実装例(C++)

#include<bits/stdc++.h>

using namespace std;

const long long INF = 0x1fffffffffffffff;

int main(){
    int n, m, k;
    cin >> n >> m >> k;
    vector<long long> c(n), a(m);
    for(int i = 0; i < n; i++){
        cin >> c[i]; c[i]--;
    }
    for(int i = 0; i < m; i++){
        cin >> a[i];
    }
    vector<vector<int>> sum(m, vector<int>(n + 1));
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            sum[i][j + 1] = sum[i][j];
            if(c[j] == i){
                sum[i][j + 1]++;
            }
        }
    }
    long long ans = INF;
    for(int i = 0; i < n - k + 1; i++){
        for(int j = 0; j < m; j++){
            int count = sum[j][i + k] - sum[j][i];
            long long cost = a[j] * (k - count);
            ans = min(ans, cost);
        }
    }
    cout << ans << endl;
}