답안 #167812

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
167812	2019-12-10T09:23:49 Z	kostia244	Lottery (CEOI18_lot)	C++17	45 / 100	132 ms	33004 KB

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.0 / 25.0

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-