Submission #120387

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
120387	2019-06-24T10:16:32 Z	raghav0307	Lottery (CEOI18_lot)	C++14	45 / 100	144 ms	59768 KB

lot

/*raghav0307 - Raghav Gupta*/

#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define pb push_back
#define fast_io() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

typedef long long ll;
typedef pair<int, int> pii;
typedef long double ld;

int dp[2005][2005];
int psum[2005][2005];

signed main(){
	fast_io();
	int n, l;
	cin >> n >> l;
	int a[n];
	for(int i = 0; i < n; i++)	cin >> a[i];
	for(int i = 0; i < n; i++){
		for(int j = 0; j < i; j++){
			if(a[i] == a[j])	continue;
			psum[i-j][max(0, j-l+1)]++;
			psum[i-j][j+1]--;
			// int cnt = l;
			// int x = i;
			// int y = j;
			// while(x >= 0 and y >= 0 and cnt > 0){
			// 	dp[x][y]++;
			// 	dp[y][x]++;
			// 	x--;
			// 	y--;
			// 	cnt--;
			// }
		}
	}
	for(int i = 1; i < n ; i++){
		int cursum = 0;
		for(int j = 0; j < n-i; j++){
			cursum += psum[i][j];
			dp[j][i+j] += cursum;
			dp[i+j][j] += cursum;
		}
	}
	int q;
	cin >> q;
	while(q--){
		int k;	cin >> k;
		for(int i = 0; i < n-l+1; i++){
			int cnt = 0;
			for(int j = 0; j < n-l+1; j++){
				if(i == j)	continue;
				if(dp[i][j] <= k)	cnt++;
				// cout << "dp[" << i << "][" << j << "] " << dp[i][j] << "\n";
			}
			cout << cnt << " ";
		}
		cout << "\n";
	}
	return 0;
}

Subtask #1

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	3 ms	1280 KB	Output is correct
3	Correct	3 ms	1280 KB	Output is correct
4	Correct	3 ms	1280 KB	Output is correct
5	Correct	3 ms	1280 KB	Output is correct
6	Correct	3 ms	1280 KB	Output is correct
7	Correct	3 ms	1280 KB	Output is correct
8	Correct	6 ms	3328 KB	Output is correct
9	Correct	6 ms	3200 KB	Output is correct
10	Correct	7 ms	3328 KB	Output is correct
11	Correct	7 ms	3328 KB	Output is correct
12	Correct	6 ms	3328 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	3 ms	1280 KB	Output is correct
3	Correct	3 ms	1280 KB	Output is correct
4	Correct	3 ms	1280 KB	Output is correct
5	Correct	3 ms	1280 KB	Output is correct
6	Correct	3 ms	1280 KB	Output is correct
7	Correct	3 ms	1280 KB	Output is correct
8	Correct	6 ms	3328 KB	Output is correct
9	Correct	6 ms	3200 KB	Output is correct
10	Correct	7 ms	3328 KB	Output is correct
11	Correct	7 ms	3328 KB	Output is correct
12	Correct	6 ms	3328 KB	Output is correct
13	Correct	101 ms	29816 KB	Output is correct
14	Correct	117 ms	29944 KB	Output is correct
15	Correct	98 ms	29916 KB	Output is correct
16	Correct	144 ms	29964 KB	Output is correct
17	Correct	143 ms	30076 KB	Output is correct
18	Correct	118 ms	30004 KB	Output is correct

Subtask #3

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	119 ms	59768 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	119 ms	59768 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	384 KB	Output is correct
2	Correct	3 ms	1280 KB	Output is correct
3	Correct	3 ms	1280 KB	Output is correct
4	Correct	3 ms	1280 KB	Output is correct
5	Correct	3 ms	1280 KB	Output is correct
6	Correct	3 ms	1280 KB	Output is correct
7	Correct	3 ms	1280 KB	Output is correct
8	Correct	6 ms	3328 KB	Output is correct
9	Correct	6 ms	3200 KB	Output is correct
10	Correct	7 ms	3328 KB	Output is correct
11	Correct	7 ms	3328 KB	Output is correct
12	Correct	6 ms	3328 KB	Output is correct
13	Correct	101 ms	29816 KB	Output is correct
14	Correct	117 ms	29944 KB	Output is correct
15	Correct	98 ms	29916 KB	Output is correct
16	Correct	144 ms	29964 KB	Output is correct
17	Correct	143 ms	30076 KB	Output is correct
18	Correct	118 ms	30004 KB	Output is correct
19	Runtime error	119 ms	59768 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
20	Halted	0 ms	0 KB	-