#include <bits/stdc++.h> #define IOSTREAM_BOOST true using namespace std; int n; vector<pair<int, int>> mines; int detonated[40]; set<int> results; int main() { #if IOSTREAM_BOOST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #endif cin >> n; for(int i = 0; i < n; i++){ int a, b; cin >> a >> b; mines.push_back({a, b}); } for(int i = 0; i < n; i++){ detonated[i] = 0; int l = mines[i].first; int r = mines[i].first; int lptr = i; int rptr = i; while(true){ bool flag = false; while(lptr >= 0 && mines[lptr].first >= l){ l = min(l, mines[lptr].first - mines[lptr].second); r = max(r, mines[lptr].first + mines[lptr].second); detonated[i] |= (1 << lptr); lptr--; flag = true; } while(rptr < n && mines[rptr].first <= r){ l = min(l, mines[rptr].first - mines[rptr].second); r = max(r, mines[rptr].first + mines[rptr].second); detonated[i] |= (1 << rptr); rptr++; flag = true; } if(!flag) break; } } for(int mask = 0; mask < (1 << n); mask++){ int cmask = 0; for(int bit = 0; bit < n; bit++) if(mask & (1 << bit)) cmask |= detonated[bit]; results.insert(cmask); } cout << results.size() << "\n"; return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | #include <bits/stdc++.h> #define IOSTREAM_BOOST true using namespace std; int n; vector<pair<int, int>> mines; int detonated[40]; set<int> results; int main() { #if IOSTREAM_BOOST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #endif cin >> n; for(int i = 0; i < n; i++){ int a, b; cin >> a >> b; mines.push_back({a, b}); } for(int i = 0; i < n; i++){ detonated[i] = 0; int l = mines[i].first; int r = mines[i].first; int lptr = i; int rptr = i; while(true){ bool flag = false; while(lptr >= 0 && mines[lptr].first >= l){ l = min(l, mines[lptr].first - mines[lptr].second); r = max(r, mines[lptr].first + mines[lptr].second); detonated[i] |= (1 << lptr); lptr--; flag = true; } while(rptr < n && mines[rptr].first <= r){ l = min(l, mines[rptr].first - mines[rptr].second); r = max(r, mines[rptr].first + mines[rptr].second); detonated[i] |= (1 << rptr); rptr++; flag = true; } if(!flag) break; } } for(int mask = 0; mask < (1 << n); mask++){ int cmask = 0; for(int bit = 0; bit < n; bit++) if(mask & (1 << bit)) cmask |= detonated[bit]; results.insert(cmask); } cout << results.size() << "\n"; return 0; } |