Submission #780884

#	Time	Username	Problem	Language	Result	Execution time	Memory
780884		boris_mihov	Advertisement 2 (JOI23_ho_t2)	C++17	59 / 100	2061 ms	3764 KiB

Main

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <stack>
#include <set>

typedef long long llong;
const int MAXN = 200000 + 10;
const int INF  = 1e9;

struct Person
{
    int x, e;
    friend bool operator > (const Person &a, const Person &b)
    {
        return a.e > b.e;
    }
};

int n;
Person p[MAXN];
bool taken[MAXN];

void solve()
{
    int ans = 0;
    std::sort(p + 1, p + 1 + n, std::greater <Person> ());
    for (int i = 1 ; i <= n ; ++i)
    {
        bool thereIs = false;
        for (int j = i - 1 ; j >= 1 ; --j)
        {
            if (taken[j] && p[j].e - p[i].e >= abs(p[i].x - p[j].x))
            {
                thereIs = true;
                break;
            }
        }
        
        if (!thereIs)
        {
            taken[i] = true;
            ans++;
        }
    }

    std::cout << ans << '\n';
}   

void input()
{
    std::cin >> n;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> p[i].x >> p[i].e;
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

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