Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- bool isDiag = false;
- vector<pair<int, int>> listV;
- int main(){
- //isDiag = true;
- freopen( "trapped.in", "r", stdin);
- int ans = 0;
- int N ;
- cin >> N ;
- int va, p;
- for (int i = 0; i < N; i++)
- {
- cin >> va >> p;
- listV.push_back({p, va});
- }
- sort(listV.begin(), listV.end());
- for (int i = 0; i < N -1; i++)
- {
- int area = listV[i+1].first - listV[i].first ;
- if(isDiag) cout << "i: " << i << ", pos: " << listV[i].first << "-" << listV[i+1].first << ", area: " << area;
- int left = i ;
- int right = i+1;
- int dist ;
- while (left >= 0 && right <= N-1)
- {
- bool broke = false;
- dist = listV[right].first - listV[left].first;
- if (dist > listV[left].second)
- {
- left--; //broke left skip to next one;
- broke = true;
- }
- if (dist > listV[right].second)
- {
- right++; //broke right skip to next none;
- broke = true;
- }
- if (!broke)
- {
- //area that
- break;
- }
- }
- bool broken = true;
- if (left >= 0 && right <= N-1)
- {
- //couldn't break out
- ans += area;
- broken = false;
- }
- if(isDiag) cout << ", broken: " << broken << ", left: " << left << ", right: " << right<< ", largest dist: " << dist << ", ans: " << ans << endl;
- }
- if(!isDiag) freopen("trapped.out", "w", stdout);
- cout << ans << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
