Submission #1267263

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267263		alexandros	Advertisement 2 (JOI23_ho_t2)	C++20	33 / 100	2095 ms	29448 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

vector<ll> X, E;

int main() {
    bool allSame = true;
    set<ll> s;
    ll amount, n, p, result = 0, sn;
    scanf("%lld", &amount);
    for(ll i = 0; i < amount; i++)
    {
        scanf("%lld %lld", &p, &n);
        if(i==0) sn = n;
        else if(n != sn) allSame = false;
        X.push_back(p);
        E.push_back(n);
        s.insert(p);
    }
    if(allSame) cout << s.size() << "\n";
    else
    {
        vector<int> cover(amount, 0);
        for (int i = 0; i < amount; i++) {
            int m = 0;
            m |= (1 << i);
            for (int j = 0; j < amount; j++) {
                if (i == j) continue;
                long long dist = llabs(X[i] - X[j]);
                long long diff = E[i] - E[j];
                if (dist <= diff) {
                    m |= (1 << j);
                }
            }
            cover[i] = m;
        }

        int fullMask = (1 << amount) - 1;
        for (int k = 1; k <= amount; k++) {
            vector<bool> isd(amount, false);
            for (int i = amount - k; i < amount; i++) {
                isd[i] = true;
            }
            do {
                int combined = 0;
                for (int i = 0; i < amount; i++) {
                    if (isd[i]) {
                        combined |= cover[i];
                    }
                }
                if (combined == fullMask) {
                    cout << k << "\n";
                    return 0;
                }
            } while (next_permutation(isd.begin(), isd.end()));
        }
        cout << amount << "\n";
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     scanf("%lld", &amount);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:16:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         scanf("%lld %lld", &p, &n);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

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