## Description

## Submission

- Counting sort
- O(200N)
- When d is even and d/2, d/2+1 lies in the middle is a special case

#include <vector>
#include <iostream>
using namespace std;
// Complete the activityNotifications function below.
int activityNotifications(vector<int> expenditure, int d) {
vector<int> count(201);
for(int i = 0; i < 201; ++i) {
count[i] = 0;
}
int nNotifications = 0;
for(int i = 0; i < d; ++i) {
count[expenditure[i]]++;
}
for(int i = d; i < expenditure.size(); ++i) {
// find the median * 2
int s = 0;
int m = 0;
for(int j = 0; j < count.size(); ++j) {
s += count[j];
if(s * 2 > d) {
m = j * 2;
break;
}
if(s * 2 == d) {
for(int k = j + 1; k < d; ++k) {
if(count[k] != 0) {
m = k + j;
break;
}
}
break;
}
}
if(expenditure[i] >= m) nNotifications++;
count[expenditure[i - d]]--;
if(i + 1 != expenditure.size()) count[expenditure[i]]++;
}
return nNotifications;
}
int main()
{
int n, d; cin >> n >> d;
vector<int> expenditure(n);
for (int i = 0; i < n; i++) {
cin >> expenditure[i];
}
int result = activityNotifications(expenditure, d);
cout << result << "\n";
return 0;
}