oj.uz

Submission #167812

# Submission time Handle Problem Language Result Execution time Memory
167812 2019-12-10T09:23:49 Z kostia244 Lottery (CEOI18_lot) C++17
45 / 100
 132 ms 33004 KB 
#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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 1148 KB Output is correct
3 Correct 3 ms 1144 KB Output is correct
4 Correct 3 ms 1144 KB Output is correct
5 Correct 3 ms 1144 KB Output is correct
6 Correct 3 ms 1144 KB Output is correct
7 Correct 3 ms 1144 KB Output is correct
8 Correct 5 ms 2808 KB Output is correct
9 Correct 5 ms 2808 KB Output is correct
10 Correct 7 ms 2808 KB Output is correct
11 Correct 7 ms 2808 KB Output is correct
12 Correct 7 ms 2808 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 1148 KB Output is correct
3 Correct 3 ms 1144 KB Output is correct
4 Correct 3 ms 1144 KB Output is correct
5 Correct 3 ms 1144 KB Output is correct
6 Correct 3 ms 1144 KB Output is correct
7 Correct 3 ms 1144 KB Output is correct
8 Correct 5 ms 2808 KB Output is correct
9 Correct 5 ms 2808 KB Output is correct
10 Correct 7 ms 2808 KB Output is correct
11 Correct 7 ms 2808 KB Output is correct
12 Correct 7 ms 2808 KB Output is correct
13 Correct 53 ms 16248 KB Output is correct
14 Correct 94 ms 16248 KB Output is correct
15 Correct 71 ms 16248 KB Output is correct
16 Correct 132 ms 16336 KB Output is correct
17 Correct 121 ms 16376 KB Output is correct
18 Correct 120 ms 16348 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 72 ms 33004 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 72 ms 33004 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 1148 KB Output is correct
3 Correct 3 ms 1144 KB Output is correct
4 Correct 3 ms 1144 KB Output is correct
5 Correct 3 ms 1144 KB Output is correct
6 Correct 3 ms 1144 KB Output is correct
7 Correct 3 ms 1144 KB Output is correct
8 Correct 5 ms 2808 KB Output is correct
9 Correct 5 ms 2808 KB Output is correct
10 Correct 7 ms 2808 KB Output is correct
11 Correct 7 ms 2808 KB Output is correct
12 Correct 7 ms 2808 KB Output is correct
13 Correct 53 ms 16248 KB Output is correct
14 Correct 94 ms 16248 KB Output is correct
15 Correct 71 ms 16248 KB Output is correct
16 Correct 132 ms 16336 KB Output is correct
17 Correct 121 ms 16376 KB Output is correct
18 Correct 120 ms 16348 KB Output is correct
19 Runtime error 72 ms 33004 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -