| 比赛 |
果蝇王邀请赛div2 |
评测结果 |
AWWWWWEEEE |
| 题目名称 |
果蝇炸弹 |
最终得分 |
10 |
| 用户昵称 |
对立猫猫对立 |
运行时间 |
1.370 s |
| 代码语言 |
C++ |
内存使用 |
26.05 MiB |
| 提交时间 |
2026-08-27 11:32:00 |
显示代码纯文本
#include <bits/stdc++.h>
#define int long long
#define MOD 1000000007
#define endl '\n'
using namespace std;
int c, n;
int a[5005], r[5005], ans;
vector<int> g[5005];
bool chk(int sit) {
for(int j = 1; j <= n; j++) {
if(sit & 1 << (j - 1)) {
for(int p : g[j]) {
if(!(sit & 1 << (p - 1))) {
return false;
}
}
}
}
return true;
}
signed main() {
freopen("bombmine.in", "r", stdin);
freopen("bombmine.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> c;
cin >> n;
if(n > 30) {
cout << "No!" << endl;
}
for(int i = 1; i <= n; i++) {
cin >> a[i] >> r[i];
}
for(int i = 1; i <= n; i++) {
int L = lower_bound(a + 1, a + n + 1, a[i] - r[i]) - a;
int R = lower_bound(a + 1, a + n + 1, a[i] + r[i] + 1) - a;
R--;
if(L >= R) continue;
else {
// cout << i << " " << L << " " << R << endl;
for(int j = L; j <= R; j++) {
if(j != i) g[i].push_back(j);
}
}
}
for(int i = 0; i <= (1 << n) - 1; i++) {
if(chk(i)) ans++;
ans %= MOD;
}
cout << ans % MOD << endl;
return 0;
}