Submission #895536

#	Time	Username	Problem	Language	Result	Execution time	Memory
895536		LiuBruh	Advertisement 2 (JOI23_ho_t2)	C++17	33 / 100	283 ms	21656 KiB

Main

#include <bits/stdc++.h>

#define int long long
#define F first
#define S second
#define sz(v) (int)v.size()
using namespace std;

const int maxn = (int)20;
const int INF = (int)1e18 + 5;

int n, an = INF;
vector<pair<int, int>> ar;
bitset<maxn> vis;

void sol2() {
    for (int i = 1; i <= n; i++) {
        int a, b;  cin >> a >> b;
        ar.push_back({a, b});
    }
    for (int mask = 0; mask < (1 << n); mask++) {
        vis.reset();
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                for (int j = 0; j < n; j++) {
                    if (abs(ar[i].F - ar[j].F) <= ar[i].S - ar[j].S) {
                        vis[j] = true;
                    }
                }
            }
        }
        if (vis.count() == n) {
            an = min(an, (long long)__builtin_popcountll(mask));
        }
    }
    cout << an << '\n';
}

set<int> st;

void sol1() {
    for (int i = 1; i <= n; i++) {
        int a, b;  cin >> a >> b;
        st.insert(a);
    }
    cout << sz(st) << '\n';
}

void solve() {
    cin >> n;
    if (n <= 16) sol2();
    else sol1();
}

/*
4
4 2
2 3
3 4
6 5

3
7 10
10 10
7 10

10
31447678 204745778
430226982 292647686
327782937 367372305
843320852 822224390
687565054 738216211
970840050 766211141
563662348 742939240
103739645 854320982
294864525 601612333
375952316 469655019
*/

signed main() {
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    solve();

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void sol2()':
Main.cpp:32:25: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   32 |         if (vis.count() == n) {
      |             ~~~~~~~~~~~~^~~~

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