Submission #68540115

---

Source Code Expand

#include <bits/stdc++.h>
#define SZ(x) ((int)(x).size())
#define ALL(x) begin(x), end(x)
#define REP(i, n) for (int i = 0; i < int(n); i++)
#define REP1(i, a, b) for (int i = (a); i <= int(b); i++)

#if __has_include("shik/dump.h")
#include "shik/dump.h"  // IWYU pragma: keep
#else
#define dump(...) 0
#endif

using namespace std;

inline void chkmin(int &a, int b) {
  if (b < a) a = b;
}

const int N = 510;
const int M = 510;
const int INF = 1e9;

int n, m, l, a[N];
void input() {
  cin >> n >> m >> l;
  REP(i, n) cin >> a[i];
}

int w[N][M], dp[2][M];
void solve() {
  REP(i, l) {
    REP(j, m) {
      int s = 0;
      for (int k = i; k < n; k += l) {
        int d = j - a[k];
        if (d < 0) d += m;
        s += d;
      }
      w[i][j] = s;
    }
  }

  int u = 0;
  REP(i, m) dp[u][i] = INF;
  dp[u][0] = 0;
  REP(i, l) {
    int v = u ^ 1;
    REP(j, m) dp[v][j] = INF;
    REP(j, m) {
      int me = dp[u][j];
      REP(k, m) {
        int wk = w[i][k];
        int nj = j + k;
        if (nj >= m) nj -= m;
        chkmin(dp[v][nj], me + wk);
      }
    }
    u ^= 1;
  }
  int ans = dp[u][0];
  cout << ans << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  input();
  solve();
  return 0;
}

Submission Info

Judge Result