Submission #1204561

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204561		loom	Lottery (CEOI18_lot)	C++20	0 / 100	534 ms	1024 KiB

lot

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 5e18
#define nl '\n'

inline void solve(){
   int n, l;
   cin>>n>>l;
   int a[n];
   for(int i=0; i<n; i++) cin>>a[i];

   int q;
   cin>>q;
   int qry[q];
   int ans[q][n];
   
   for(int i=0; i<q; i++){
      int k;
      cin>>k;
      qry[i] = k;
   }

   int ldp[n], dp[n];
   vector<int> pre(n);

   for(int j=0; j+l-1<n; j++){
      ldp[j] = 0;
      for(int k=0; k<l; k++){
         if(a[k] != a[j+k]) ldp[j]++;
      }
      pre[ldp[j]]++;
   }

   for(int j=1; j<n; j++) pre[j] += pre[j-1];
   for(int j=0; j<q; j++) ans[j][0] = pre[qry[j]];

   for(int i=1; i+l-1<n; i++){
      dp[0] = 0;
      for(int k=0; k<l; k++){
         if(a[i+k] != a[k]) dp[0]++;
      }

      fill(pre.begin(), pre.end(), 0);
      pre[dp[0]]++;

      for(int j=1; j+l-1<n; j++){
         dp[j] = ldp[j-1] - (a[i-1] != a[j-1]) + (a[i] != a[j]);
         pre[dp[j]]++;
      }

      for(int j=1; j<n; j++) pre[j] += pre[j-1];
      for(int j=0; j<q; j++) ans[j][i] = pre[qry[j]];

      for(int j=0; j<n; j++) swap(ldp[j], dp[j]);
   }

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

signed main(){
   ios_base::sync_with_stdio(0);
   cin.tie(NULL);cout.tie(NULL);

   int t = 1;
   //cin>>t;
   while(t--) solve();

   return 0;
}

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