Submission #1196881

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196881		LucaLucaM	Lottery (CEOI18_lot)	C++20	100 / 100	337 ms	8320 KiB

lot

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using ll = long long;
#define debug(x) #x << " = " << x << '\n'

const int NMAX = 1e4;
const int QMAX = 1e2;

int a[NMAX + 1];
int nw[NMAX + 1];
int old[NMAX + 1];
int f[NMAX + 1];
int answer[QMAX][NMAX + 1];

int main() {
  #ifdef LOCAL
    freopen("input.txt", "r", stdin);
  #endif

  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
  std::cout.tie(0);
  
  int n, L;
  std::cin >> n >> L;

  for (int i = 1; i <= n; i++) {
    std::cin >> a[i];
  }
  
  int q;
  std::cin >> q;
  std::vector<int> k(q);
  for (int &x : k) {
    std::cin >> x;
  }
  
  for (int i = n; i > 0; i--) {
    for (int j = n; j > 0; j--) {
      nw[j] = old[j + 1] + (a[i] != a[j]);
      if (i + L <= n && j + L <= n) {
        nw[j] -= (a[i + L] != a[j + L]);
      }
    }
    if (i + L - 1 <= n) {
      for (int j = 1; j <= n - L + 1; j++) {
        f[nw[j]]++;
      }
      for (int j = 1; j <= L; j++) {
        f[j] += f[j - 1];
      }
      for (int iq = 0; iq < q; iq++) {
        answer[iq][i] += f[k[iq]];
      }
      for (int j = 0; j <= L; j++) {
        f[j] = 0;
      }
    }
    for (int j = 1; j <= n; j++) {
      old[j] = nw[j];
    }
  }

  for (int iq = 0; iq < q; iq++) {
    for (int i = 1; i <= n - L + 1; i++) {
      std::cout << answer[iq][i] - 1 << ' ';
    }
    std::cout << '\n';
  }
  
  return 0;
}

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