제출 #599774

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
599774		CSQ31	Lottery (CEOI18_lot)	C++17	100 / 100	1814 ms	8396 KiB

lot

#include <bits/stdc++.h>
using namespace std;
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
typedef long long int ll;
#define all(a) a.begin(),a.end()
int a[10005],b[10005];
int ans[105][10005];
int nearest[10005];
int main()
{
	owo
	int n,l;
	cin>>n>>l;
	for(int i=0;i<n;i++)cin>>a[i];
	int q;
	cin>>q;
	vector<array<int,2>>qu;
	for(int i=0;i<q;i++){
		int k;
		cin>>k;
		qu.push_back({l-k,i});
		//>=l-k matches
	}
	sort(all(qu));
	for(int i=0;i<=n;i++){
		nearest[i] = -1;
		for(int j=0;j<q;j++){
			if(i >= qu[j][0])nearest[i] = j;
		}
		//cout<<nearest[i]<<" ";
	}
	//cout<<'\n';
	for(int i=-n+1;i<n;i++){
		if(i==0)continue;
		for(int j=0;j<n;j++){
			if(j+i>=0 && j+i<n && a[j] == a[i+j])b[j] = 1;	
		}
		for(int j=1;j<n;j++)b[j]+=b[j-1];
		for(int j=max(0,-i);j<min(n-l+1,n-l-i+1);j++){ //i am shiftng by i
			int num = b[j+l-1] - (j?b[j-1]:0);
		    //for(int k=0;k<q;k++)if(num >= qu[k][0])ans[qu[k][1]][j]++;
			if(nearest[num] != -1){
				int idx = nearest[num];
				ans[idx][j]++;
			}
		}
		for(int j=0;j<n;j++)b[j] = 0;
	}
	for(int i=q-2;i>=0;i--){
		for(int j=0;j<n;j++)ans[i][j]+=ans[i+1][j];
	}
	for(int i=0;i<q;i++){
		for(int j=0;j<q;j++){
			if(qu[j][1] == i){
				for(int k=0;k<n-l+1;k++)cout<<ans[j][k]<<" ";
				cout<<'\n';
				break;
			}
			
		}
		
	}
	
	
}

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