Submission #1214064

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214064		lopkus	Lottery (CEOI18_lot)	C++20	45 / 100	63 ms	131072 KiB

lot

#include <bits/stdc++.h>

#define int int64_t

signed main() {
  int n, l;
  std::cin >> n >> l;
  std::vector<int> a(n + 1);
  for(int i = 1; i <= n; i++) {
    std::cin >> a[i];
  }
  std::vector<std::vector<int>> pref(n + 2, std::vector<int>(n + 1));
  for(int j = 1; j <= n; j++) {
    for(int i = n; i >= 1; i--) {
      pref[i][j] = pref[i + 1][j];
      if(i + j <= n) {
        pref[i][j] += (a[i] != a[i + j]);
      }
    }
  }
  int q;
  std::cin >> q;
  while(q--) {
    int k;
    std::cin >> k;
    std::vector<int> ans(n + 1);
    for(int i = 1; i + l - 1 <= n; i++) {
      for(int j = i + 1; j + l - 1 <= n; j++) {
        int s = j - i;
        if(pref[i][s] - pref[i + l][s] <= k) {
          ans[i] += 1;
          ans[j] += 1;
        }
      }
    }
    for(int i = 1; i + l - 1 <= n; i++) {
      std::cout << ans[i] << " ";
    }
    std::cout << "\n";
  }
}

• Subtask 1: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20