제출 #955602

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
955602		Kakarot	Advertisement 2 (JOI23_ho_t2)	C++98	59 / 100	2023 ms	2396 KiB

Main

#include <bits/stdc++.h>
#define int int64_t
using namespace std;

void setIO() {
    cin.tie(0)->sync_with_stdio(0);
}

bool pred(pair<int, int> &src, pair<int, int> &dest) {
    return (abs(src.first - dest.first) <= src.second - dest.second);
}

void mark(int idx, vector<bool> &marked, vector<pair<int, int>> &points) {
    if(marked[idx]) return;
    marked[idx] = true;
    for(int i = 0; i < idx; i++) {
        if(marked[i] or !pred(points[idx], points[i])) continue;
        mark(i, marked, points);
    }
}

void solve() {
    //cout << "zco";
    int n;
    cin >> n;
    vector<pair<int, int>> points(n);
    for(auto &x : points) cin >> x.first >> x.second;
    sort(points.begin(), points.end(), [](pair<int, int> &a, pair<int, int> &b) { return a.second < b.second; });
    int ans = 0;
    vector<bool> marked(n, false);
    for(int i = n-1; i > -1; i--) {
        if(marked[i]) continue;
        mark(i, marked, points);
        ans++;
    }    
    cout << ans;
}

int32_t main() {
    setIO();
    solve();
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 23 / 23
• Subtask 3: 36 / 36
• Subtask 4: 0 / 31