Submission #467990

#	Time	Username	Problem	Language	Result	Execution time	Memory
467990		ivan_tudor	Lottery (CEOI18_lot)	C++14	45 / 100	68 ms	65540 KiB

lot

#include<bits/stdc++.h>
using namespace std;
const int N = 10005;
int scor[N][N];
int ans[N][N];
int v[N];
int l;
int getscor(int x, int y){
  int ans = 0;
  for(int i = 0; i < l; i++){
    if(v[x + i] != v[y + i])
      ans++;
  }
  return ans;
}
int main()
{
  //freopen(".in","r",stdin);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  int n;
  cin>>n>>l;
  for(int i = 1; i<=n; i++)
    cin>>v[i];
  for(int i = 2; i <= n - l + 1; i++){
    scor[1][i] = getscor(1, i);
  }
  for(int i = 2; i <= n - l + 1; i++){
    for(int j = i + 1; j <= n - l + 1; j++){
      scor[i][j] = scor[i - 1][j - 1] - (v[i - 1] != v[j - 1]) + (v[i + l -1] != v[j + l - 1]);
    }
  }
  for(int i = 1; i <= n -l + 1; i++){
    for(int j = i + 1; j <= n- l + 1; j++){
      ans[i][scor[i][j]]++;
      ans[j][scor[i][j]]++;
    }
  }
  for(int i =1 ; i<=n -l + 1; i++){
    for(int j = 0; j<= l; j++)
      if(j)
        ans[i][j] += ans[i][j - 1];
  }
  int q;
  cin>>q;
  for(int i =1 ; i<=q; i++){
    int k;
    cin>>k;
    for(int j = 1; j <= n -l + 1; j++)
      cout<<ans[j][k]<<" ";
    cout<<"\n";
  }
  return 0;
}

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