Submission #1275253

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275253		danieldcv	Gym Badges (NOI22_gymbadges)	C++20	15 / 100	2094 ms	8256 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef set<int> si;
typedef map<int, int> mii;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define mp make_pair
#define rep(i, a, b) for(int i = a; i < b; i++)
#define sz(x) (int)x.size()
#define pc __builtin_popcountll
#define msb(x) 31 - __builtin_clz(x)
#define lsb(x) __builtin_ctz(x)
const int INF = 1e9 + 1;
const ll LLINF = 1e18 + 1;
const int MOD = 1e9 + 7;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
/* 

*/
 
void solve() {
    int n; cin >> n;
    vi x(n), l(n);
    for (int i = 0; i < n; i++) cin >> x[i];
    for (int i = 0; i < n; i++) cin >> l[i];
    vector<bool> ok(1 << n);
    ok[0] = 1;
    int ans = 0;
    for (int mask = 1; mask < (1 << n); mask++) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if ((mask >> i) & 1) {
                sum += x[i];
            }
        }
        for (int i = 0; i < n; i++) {
            if ((mask >> i) & 1) {
                if (!ok[mask ^ (1 << i)]) continue;
                if (sum - x[i] <= l[i]) {
                    ans = max(ans, 1LL * pc(mask));
                    ok[mask] = 1;
                }
            }
        }
    }
    cout << ans << '\n';
}
 
signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    // int t; cin >> t; while (t--) solve();
    solve();
    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 0 / 9
• Subtask 3: 0 / 27
• Subtask 4: 0 / 49