Submission #1322474

#TimeUsernameProblemLanguageResultExecution timeMemory
1322474cubedAdvertisement 2 (JOI23_ho_t2)C++20
59 / 100
2094 ms5232 KiB
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define f first
// #define s second
#define pb(x) push_back(x)
#define int long long


/*
ORDERED SET PDBS

#include <bits/extc++.h>
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
*/

const int MOD = 1e9+7;
const int inf = 1e9;
const int INF = 1e18+20;
const int LOG = 25;

/*
n<=1000


*/
int n;

vector<pair<int, int>> a;

vector<pair<int, int>> given;

int ans = inf;

/*void f (int i) {
    if (i==n) {
        int reached=0;
        vector<int> tt(n, 0);

        for (auto x:given) {
            for (int i=0;i<n; i++) {
                if (abs(x.first - a[i].first) <= x.second - a[i].second && !tt[i]) {
                    reached++;
                    tt[i]=1;
                }
            }
        }

        if (reached==n) {
            ans=min(ans, cnt);
        }

        return;
    }

    // donate the book to this guy
    given.push_back(a[i]);
    cnt++;
    f(i+1);
    given.pop_back();
    cnt--;

    // do not donate the book to this guy
    f(i+1);
}*/

void solve() {
    cin>>n;

    a.resize(n);
    vector<pair<int, int>> maxi(n);
    for (int i=0; i<n; i++) {
        cin>>a[i].first>>a[i].second;
        maxi[i] = {a[i].second, i};
    }

    vector<int> tt(n, 0);

    for (int i=0; i<n; i++)

    sort(maxi.begin(), maxi.end(), greater<>());

    int reached = 0;
    int cnt=0;

    vector<int> vis(n, 0);

    for (auto i : maxi) {
        int idx = i.second;
        if (!vis[idx]) cnt++;

        for (int j=0; j<n; j++) {
            if (vis[j]) continue;

            if (abs(a[idx].first - a[j].first) <= a[idx].second - a[j].second) {
                reached++;
                vis[j]=1;
            }
        }

        if (reached==n) break;
    }

    cout<<cnt<<endl;

    

}

bool multi=false;

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
  
    int t=1;
    if (multi) cin>>t;
 
    while (t--) solve();
 
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...