oj.uz

Submission #126087

# Submission time Handle Problem Language Result Execution time Memory
126087 2019-07-07T02:54:07 Z briansu Lottery (CEOI18_lot) C++14
80 / 100
 3000 ms 3500 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
#define REP(i, n) for(int i = 0;i < n;i ++)
#define REP1(i, n) for(int i = 1;i <= n;i ++)
#define FILL(i, n) memset(i, n, sizeof(i))
#define X first
#define Y second
#define pb push_back
#define SZ(_a) ((int)(_a).size())
#define ALL(_a) (_a).begin(), (_a).end()
#ifdef brian
#define IOS()
template<typename T>void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...t> void _do(T &&x, t &&...X){cerr<<x<<", ";_do(X...);}
#define debug(...) {\
	fprintf(stderr, "%s - %d (%s) = ", __PRETTY_FUNCTION__, __LINE__, #__VA_ARGS__);\
	_do(__VA_ARGS__);\
}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define debug(...)
#define endl '\n'
#endif

const ll MAXn = 1e4 + 5;
const ll INF = ll(1e17);
const ll MOD = 1000000007;
const ll bs = 880301;

int dt[MAXn];
int qr[MAXn];

int d[MAXn], a[105][MAXn];

int main(){
	IOS();
	ll n, l;
	cin>>n>>l;
	REP1(i, n)cin>>d[i];
	ll q;
	cin>>q;
	REP1(i, q)cin>>qr[i];

	REP1(dif, n)
	{
		REP1(j, n - dif)dt[j] = (d[j] != d[j + dif]) + dt[j-1];
		REP1(t, q)REP1(i, n - l + 1 - dif)if(dt[i + l - 1] - dt[i - 1] <= qr[t])a[t][i] ++, a[t][i + dif] ++;
	}

	REP1(t, q)REP1(i, n - l + 1)cout<<a[t][i]<<" \n"[i == n - l + 1];
}

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 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 508 KB Output is correct
10 Correct 4 ms 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 4 ms 504 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 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 508 KB Output is correct
10 Correct 4 ms 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 4 ms 504 KB Output is correct
13 Correct 25 ms 504 KB Output is correct
14 Correct 29 ms 376 KB Output is correct
15 Correct 18 ms 504 KB Output is correct
16 Correct 40 ms 760 KB Output is correct
17 Correct 36 ms 632 KB Output is correct
18 Correct 36 ms 504 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 544 KB Output is correct
2 Correct 206 ms 504 KB Output is correct
3 Correct 195 ms 504 KB Output is correct
4 Correct 193 ms 632 KB Output is correct
5 Correct 161 ms 504 KB Output is correct
6 Correct 189 ms 504 KB Output is correct
7 Correct 172 ms 604 KB Output is correct
8 Correct 196 ms 632 KB Output is correct
9 Correct 197 ms 632 KB Output is correct
10 Correct 194 ms 632 KB Output is correct
11 Correct 17 ms 376 KB Output is correct
12 Correct 143 ms 504 KB Output is correct
13 Correct 166 ms 588 KB Output is correct
14 Correct 165 ms 692 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 544 KB Output is correct
2 Correct 206 ms 504 KB Output is correct
3 Correct 195 ms 504 KB Output is correct
4 Correct 193 ms 632 KB Output is correct
5 Correct 161 ms 504 KB Output is correct
6 Correct 189 ms 504 KB Output is correct
7 Correct 172 ms 604 KB Output is correct
8 Correct 196 ms 632 KB Output is correct
9 Correct 197 ms 632 KB Output is correct
10 Correct 194 ms 632 KB Output is correct
11 Correct 17 ms 376 KB Output is correct
12 Correct 143 ms 504 KB Output is correct
13 Correct 166 ms 588 KB Output is correct
14 Correct 165 ms 692 KB Output is correct
15 Correct 222 ms 548 KB Output is correct
16 Correct 189 ms 604 KB Output is correct
17 Correct 203 ms 612 KB Output is correct
18 Correct 194 ms 632 KB Output is correct
19 Correct 194 ms 632 KB Output is correct
20 Correct 195 ms 612 KB Output is correct
21 Correct 204 ms 632 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 508 KB Output is correct
10 Correct 4 ms 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 4 ms 504 KB Output is correct
13 Correct 25 ms 504 KB Output is correct
14 Correct 29 ms 376 KB Output is correct
15 Correct 18 ms 504 KB Output is correct
16 Correct 40 ms 760 KB Output is correct
17 Correct 36 ms 632 KB Output is correct
18 Correct 36 ms 504 KB Output is correct
19 Correct 280 ms 544 KB Output is correct
20 Correct 206 ms 504 KB Output is correct
21 Correct 195 ms 504 KB Output is correct
22 Correct 193 ms 632 KB Output is correct
23 Correct 161 ms 504 KB Output is correct
24 Correct 189 ms 504 KB Output is correct
25 Correct 172 ms 604 KB Output is correct
26 Correct 196 ms 632 KB Output is correct
27 Correct 197 ms 632 KB Output is correct
28 Correct 194 ms 632 KB Output is correct
29 Correct 17 ms 376 KB Output is correct
30 Correct 143 ms 504 KB Output is correct
31 Correct 166 ms 588 KB Output is correct
32 Correct 165 ms 692 KB Output is correct
33 Correct 222 ms 548 KB Output is correct
34 Correct 189 ms 604 KB Output is correct
35 Correct 203 ms 612 KB Output is correct
36 Correct 194 ms 632 KB Output is correct
37 Correct 194 ms 632 KB Output is correct
38 Correct 195 ms 612 KB Output is correct
39 Correct 204 ms 632 KB Output is correct
40 Correct 1718 ms 1876 KB Output is correct
41 Correct 160 ms 760 KB Output is correct
42 Correct 1083 ms 2168 KB Output is correct
43 Correct 975 ms 1912 KB Output is correct
44 Correct 975 ms 1784 KB Output is correct
45 Execution timed out 3045 ms 3500 KB Time limit exceeded
46 Halted 0 ms 0 KB -