제출 #1287527

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1287527		bnijaamaa	Topical (NOI23_topical)	C++20	61 / 100	1099 ms	85788 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define nn '\n'

map<pair<vector<int>, vector<bool>>, int> memo;

int dfs(vector<vector<int>>& r, vector<vector<int>>& u, vector<int>& p, vector<bool>& used, int n, int k) {
    auto key = make_pair(p, used);
    if (memo.count(key)) return memo[key];

    int max_completed = 0;

    for (int i = 0; i < n; ++i) {
        if (used[i]) continue;

        bool can_do = true;
        for (int j = 0; j < k; ++j) {
            if (p[j] < r[i][j]) {
                can_do = false;
                break;
            }
        }

        if (can_do) {
            used[i] = true;
            for (int j = 0; j < k; ++j)
                p[j] += u[i][j];

            max_completed = max(max_completed, 1 + dfs(r, u, p, used, n, k));

            for (int j = 0; j < k; ++j)
                p[j] -= u[i][j];
            used[i] = false;
        }
    }

    return memo[key] = max_completed;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    if (n == 1) {
        vector<vector<int>> r(n, vector<int>(k));
        vector<vector<int>> u(n, vector<int>(k));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < k; j++)
                cin >> r[i][j];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < k; j++)
                cin >> u[i][j];

        bool can_do = true;
        for (int j = 0; j < k; j++) {
            if (r[0][j] > 0) {
                can_do = false;
                break;
            }
        }
        cout << (can_do ? 1 : 0) << nn;
    }
    else if (k == 1) {
        vector<int> a(n), b(n);
        vector<pair<int, int>> p;
        for (int i = 0; i < n; i++) cin >> a[i];
        for (int i = 0; i < n; i++) cin >> b[i];
        for (int i = 0; i < n; i++) p.pb({a[i], b[i]});

        sort(p.begin(), p.end());
        int cnt = 0, sum = 0;
        for (int i = 0; i < n; i++) {
            if (sum >= p[i].first) {
                sum += p[i].second;
                cnt++;
            }
        }
        cout << cnt << nn;
    }
    else {
        vector<vector<int>> r(n, vector<int>(k));
        vector<vector<int>> u(n, vector<int>(k));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < k; j++)
                cin >> r[i][j];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < k; j++)
                cin >> u[i][j];

        vector<int> p(k, 0);
        vector<bool> used(n, false);
        cout << dfs(r, u, p, used, n, k) << nn;
    }
}

• Subtask 1: 12 / 12
• Subtask 2: 28 / 28
• Subtask 3: 21 / 21
• Subtask 4: 0 / 39