Submission #570198

#	Time	Username	Problem	Language	Result	Execution time	Memory
570198		MarcosPauloEvers	Lottery (CEOI18_lot)	C++17	45 / 100	3084 ms	4728 KiB

lot

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e4 + 10, MAXQ = 110;
int n, l, q;
int arr[MAXN];
int bit[MAXN][MAXQ];
int ans[MAXQ][MAXN];
vector<pair<int, int> > qry;

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> l;
	for(int i = 0; i < n; i++)
		cin >> arr[i];

	cin >> q;
	for(int i = 0, k; i < q; i++)
		cin >> k, qry.emplace_back(k, i);
	
	sort(begin(qry), end(qry));
	for(int i = 0; i <= n - l; i++)
	{
		for(int j = 0; j < i; j++)
		{
			int dst = 0;
			for(int k = 0; k < l; k++)
				dst += arr[i + k] != arr[j + k];
			int qtd = lower_bound(begin(qry), end(qry), make_pair(dst, 0)) - begin(qry);

			bit[i][qtd]++;
			bit[j][qtd]++;
		}
	}
	for(int j = 0; j <= n - l; j++)
		for(int i = 0, acc = 0; i < q; i++)
			acc += bit[j][i], ans[qry[i].second][j] = acc;
	
	for(int i = 0; i < q; i++)
	{
		for(int j = 0; j <= n - l; j++)
			cout << ans[i][j] << " ";
		cout << "\n";
	}
	return 0;
}

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