Submission #798865

#	Time	Username	Problem	Language	Result	Execution time	Memory
798865		vjudge1	Advertisement 2 (JOI23_ho_t2)	C++14	10 / 100	110 ms	4280 KiB

Main

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define fi first
#define se second
#define ll long long
using namespace std ;
using namespace __gnu_pbds;
const int N = 5e5 ;
bool flag1, us[N + 1] ;
int n, ans ;
//map<int, int> mp ;
pair<int, int> p[N + 1] ;
//vector<pair<int, int>> v, us ;
signed main()
{
    ios_base::sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cout.tie( 0 ) ;
    cin >> n ;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> p[i].fi >> p[i].se ;
        if(p[i].se != p[1].se)
            flag1 = 1 ;
//        mp[p[i].fi] = max(mp[p[i].fi], p[i].se) ;
    }
    if(!flag1)
    {
        ans = 1 ;
        sort(p + 1, p + n + 1) ;
        for(int i = 1 ; i < n ; i++)
            ans += (p[i].fi != p[i + 1].fi) ;
        cout << ans ;
        return 0 ;
    }
    if(n <= 16)
    {
        ans = 1e9 ;
        for(int i = 0 ; i < (1 << n) ; i++)
        {
            int now = 0, cnt = 0 ;
            bool us[n + 1] = {} ;
            for(int j = 0 ; j < n ; j++)
                if((1 << j) & i)
                {
                    us[j + 1] = 1 ;
                    now++ ;
                    for(int q = 1 ; q <= j ; q++)
                        if(abs(p[q].fi - p[j + 1].fi) <= p[j + 1].se - p[q].se)
                            us[q] = 1 ;
                }
            for(int j = 1 ; j <= n ; j++)
                cnt += us[j] ;
            if(cnt == n)
            {
//                cout << i << ' ' << now << '\n' ;
                ans = min(ans, now) ;
            }
        }
        cout << ans << '\n' ;
        return 0 ;
    }
    return 0 ;
}

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