Submission #795928

#	Time	Username	Problem	Language	Result	Execution time	Memory
795928		parsadox2	Lottery (CEOI18_lot)	C++14	100 / 100	921 ms	8408 KiB

lot

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e4 + 5 , maxq = 1e2 + 5;
int ans[maxn][maxq] , las[maxn] , ar[maxn] , n , q , l , qry[maxn] , dp[maxn] , sum[maxn];

int solve(int fir)
{
	int res = 0;
	for(int i = 0 ; i < l ; i++)  
	{
		//cout << fir << " " << i << " " << ar[fir + i] << " " << ar[n - l + i] << endl;
		if(ar[fir + i] != ar[n - l + i])
			res++;
	}
	//cout << res << endl;
	return res;
}

signed main()
{
	cin >> n >> l;
	for(int i = 0 ; i < n ; i++)
		cin >> ar[i];
	cin >> q;
	for(int i = 0 ; i < q ; i++)
		cin >> qry[i];
	for(int i = 0 ; i + l <= n ; i++)
	{
		las[i] = solve(i);
		dp[i] = las[i];
		//cout << n - l << " " << i << " " << las[i] << endl;
		sum[dp[i]]++;
	}
	for(int i = 1 ; i <= l ; i++)
		sum[i] += sum[i - 1];
	for(int i = 0 ; i < q ; i++)
		ans[n - l][i] = sum[qry[i]] - 1;
	for(int i = n - l - 1 ; i > -1 ; i--)
	{
		for(int j = 0 ; j < n - l ; j++)
		{
			dp[j] = dp[j + 1];
			if(ar[i + l] != ar[j + l])
				dp[j]--;
			if(ar[i] != ar[j])
				dp[j]++;
			//cout << i << " " << j << " " << dp[j] << endl;
		}
		dp[n - l] = las[i];
		for(int j = 0 ; j <= l ; j++)
			sum[j] = 0;
		for(int j = 0 ; j <= n - l ; j++)
			sum[dp[j]]++;
		for(int j = 1 ; j <= l ; j++)
			sum[j] += sum[j - 1];
		for(int j = 0 ; j < q ; j++)
			ans[i][j] = sum[qry[j]] - 1;
	}
	for(int i = 0 ; i < q ; i++)  
	{
		for(int j = 0 ; j <= n - l ; j++)
			cout << ans[j][i] << " ";
		cout << '\n';
	}
	return 0;
}

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