Submission #918276

#	Time	Username	Problem	Language	Result	Execution time	Memory
918276		amirhoseinfar1385	Lottery (CEOI18_lot)	C++17	100 / 100	552 ms	8440 KiB

lot

#include<bits/stdc++.h>
using namespace std;
const int maxn=10000+5,maxq=100+2;
int q,n,l,dp[2][maxn],all[maxn],res[maxn][maxq],nx[maxn];
vector<int>allq,asly;

int main(){
	cin>>n>>l;
	for(int i=1;i<=n;i++){
		cin>>all[i];
	}
	cin>>q;
	allq.resize(q);
	asly.resize(q);
	for(int i=0;i<q;i++){
		cin>>asly[i];
		allq[i]=asly[i];
	}
	sort(allq.begin(),allq.end());
	allq.resize(unique(allq.begin(),allq.end())-allq.begin());
	for(int i=0;i<maxn;i++){
		int p=lower_bound(allq.begin(),allq.end(),i)-allq.begin();
		nx[i]=p;
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<=n;j++){
			swap(dp[0][j],dp[1][j]);
		}
		for(int j=0;j<i;j++){
			if(j==0){
				dp[1][j]=l;
				continue;
			}
			dp[1][j]=dp[0][j-1];
			if(all[i]!=all[j]){
				dp[1][j]++;
			}
			if((j-1)-l+1<1||all[(j-1)-l+1]!=all[(i-1)-l+1]){
				dp[1][j]--;
			}
			if(j>=l){
				res[j][nx[dp[1][j]]]++;
				res[i][nx[dp[1][j]]]++;
			}
			//cout<<i<<" "<<j<<" "<<dp[1][j]<<"\n";
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<q;j++){
			res[i][j]+=res[i][j-1];
		}
	}
	for(int i=0;i<q;i++){
		int p=lower_bound(allq.begin(),allq.end(),asly[i])-allq.begin();
		for(int j=l;j<=n;j++){
			cout<<res[j][p]<<" ";
		}
		cout<<"\n";
	}
}

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