Submission #37161682

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N, K, D;
  cin >> N >> K >> D;
  vector<int64_t> a(N);
  for (int n = 0; n < N; ++n) {
    cin >> a[n];
  }

  unordered_map<int, unordered_map<int, int64_t>> dp;
  for (int n = 0; n < N; ++n) {
    auto prev = dp;
    if (dp[1][a[n]%D] < a[n]) {
      dp[1][a[n]%D] = a[n];
    }
    for (auto [k, v] : prev) {
      if (k == K) continue;
      for (auto [d, sum] : v) {
        auto dd = (d + a[n]) % D;
        if (dp[k+1][dd] < sum + a[n]) {
          dp[k+1][dd] = sum + a[n];
        }
      }
    }
  }
  if (dp[K].count(0)) {
    cout << dp[K][0] << endl;
  } else {
    cout << -1 << endl;
  }
}

Submission Info

Judge Result