Submission #1204573

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204573		loom	Lottery (CEOI18_lot)	C++20	100 / 100	247 ms	12336 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++) cin>>qry[i];

   vector<int> ldp(n), dp(n), pre(l+1);

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

   for(int j=1; j<=l; 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+l-1] != a[j+l-1]);
         pre[dp[j]]++;
      }

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

      swap(ldp, dp);
   }

   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: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20