Submission #167812

#	Time	Username	Problem	Language	Result	Execution time	Memory
167812		kostia244	Lottery (CEOI18_lot)	C++17	45 / 100	132 ms	33004 KiB

lot

#include<bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
using namespace std;
using ll = long long;
using vi = vector<int>;
short cmp[2020][2020], dp[2020][2020];
int n, l, q;
vi a;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> l;
	a.resize(n);
	for(auto &i : a)cin >> i;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			dp[i][j] = a[i]!=a[j];
	int cmped = 0;
	for(int k = 0; (1<<k) <= l; k++) {
		if((1<<k)&l) {
			for(int i = 0; i < n; i++) {
				for(int j = i+1; j < n; j++) {
					cmp[i][j] += dp[i+cmped][j+cmped];
				}
			}
			cmped += (1<<k);
		}
		for(int i = 0; i+(1<<k) < n; i++) {
			for(int j = i+1; j+(1<<k) < n; j++) {
				dp[i][j] += dp[i+(1<<k)][j+(1<<k)];
			}
		}
	}
	int q, z;
	cin >> q;
	int ans[10010];
	while(q--) {
		cin >> z;
		memset(ans, 0, sizeof ans);
		for(int i = 0; i+l-1 < n; i++) {
			for(int j = i+1; j+l-1 < n; j++)
				ans[i] += cmp[i][j]<=z, ans[j]+=cmp[i][j]<=z;
			cout << ans[i] << ' ';
		}
		cout << '\n';
	}
}

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