제출 #1282774

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1282774		julia_08	Lottery (CEOI18_lot)	C++20	0 / 100	1 ms	572 KiB

lot

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

const int MAXN = 2e3 + 10;
const int MAXQ = 110;

int a[MAXN];

int ans[MAXN][MAXQ];

int main(){
  cin.tie(0)->sync_with_stdio(0);

  int n, l; cin >> n >> l;

  for(int i=1; i<=n; i++) cin >> a[i];

  int q; cin >> q;

  vector<pair<int, int>> queries(q);

  for(int i=0; i<q; i++){
    int k; cin >> k;
    queries[i] = {l - k, i};
  }

  sort(queries.begin(), queries.end());

  for(int d=1; d<n; d++){
    
    int p = 0;

    int sum = 0, id = -1;

    for(int i=1; i<=(n - l + 1 - d); i++){

      while(p < i + l - 1){

        p ++;

        if(p + d <= n) sum += (a[p] == a[p + d]);
        if(id + 1 < q) if(sum >= queries[id + 1].first) id ++;

      }

      if(id >= 0){
        ans[i][id] ++;
        ans[i + d][id] ++;
      }
  
      if(i + d <= n) sum -= (a[i] == a[i + d]); 
      if(id >= 0) if(sum < queries[id].first) id --;

    }

  }

  for(int i=1; i<=n; i++){
    for(int j=(q - 2); j>=0; j--){
      ans[i][j] += ans[i][j + 1];
    }
  }

  for(int i=0; i<q; i++){
    for(int j=1; j<=(n - l + 1); j++) cout << ans[j][queries[i].second] << " ";
    cout << "\n";
  }

  return 0;
}

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