下面代码复杂度是 O(n2) 的,显然会超时,理应在 80 分上下,但是却可以 AC。
#include <bits/stdc++.h>
const int N = 1e5 + 10;
int n, m, t, a[N], cnt[N];
std::pair<int, int> offer[N];
std::unordered_set<int> ans;
int main() {
std::cin >> n >> m >> t;
for (int i = 0; i < m; ++i)
std::cin >> offer[i].first >> offer[i].second;
for (int i = 1; i <= t; ++i) {
memset(cnt, 0, sizeof(cnt));
for (int j = 0; j < m; ++j)
if (offer[j].first == i) ++cnt[offer[j].second];
for (int j = 1; j <= n; ++j) {
if (cnt[j]) a[j] += 2 * cnt[j];
else a[j] = std::max(a[j] - 1, 0);
if (a[j] > 5) ans.insert(j);
if (a[j] <= 3) ans.erase(j);
}
}
std::cout << ans.size() << std::endl;
return 0;
}