比赛 果蝇王邀请赛div2 评测结果 EEEEEEEEEE
题目名称 果蝇炸弹 最终得分 0
用户昵称 赵飞羽 运行时间 1.605 s
代码语言 C++ 内存使用 22.51 MiB
提交时间 2026-08-27 11:14:04
显示代码纯文本
#include <bits/stdc++.h>
#define int long long
using namespace std;

constexpr int N = 5010, MOD = 1e9 + 7;
int c, n, a[N], r[N], f[N], ans = 1;
vector <int> b[N];

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	freopen("bombmine.in", "r", stdin);
	freopen("bombmine.out", "w", stdout);
	cin >> c >> n;
	for (int i = 1; i <= n; i++) cin >> a[i] >> r[i];
	for (int i = 1; i <= n; i++) {
		f[i] = 1;
		for (int j = i + 1; j <= n; j++) {
			if (a[i] + r[i] < a[j] && a[j] - r[j] > a[i]) {
				/*int flg = 0;
				for (int k = i + 1; k < j; k++) {
					for (int l = 0; l < b[k])
				}
				if (!flg) */b[i].push_back(a[j]);
			}
		}
	}
	for (int i = n; i >= 1; i--) {
		for (int j = 0; j < b[i].size(); j++) {
			f[i] = (f[i] + f[b[i][j]]) % MOD;
		}
	}
//	cout << "\n";
//	for (int i = 1; i <= n; i++) {
//		for (int j = 0; j < b[i].size(); j++) {
//			cout << b[i][j] << " ";
//		}
//		cout << "\n";
//	}
//	for (int i = 1; i <= n; i++) cout << f[i] << " ";
//	cout << "\n\n";
	for (int i = 1; i <= n; i++) ans = (ans + f[i]) % MOD;
	cout << ans + 1;
	return 0;
}