Submission #1270253

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270253		duckpham27	Topical (NOI23_topical)	C++20	61 / 100	1094 ms	134040 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

// ======================= SUBTASK 1 =======================
void solve_sub1(int n, int k, vector<vector<ll>> &r, vector<vector<ll>> &u)
{
    bool ok = true;
    for (int j = 0; j < k; j++)
    {
        if (r[0][j] > 0)
            ok = false;
    }
    if (ok)
        cout << 1 << "\n";
    else
        cout << 0 << "\n";
}

// ======================= SUBTASK 2 =======================
// Brute-force cho n, k <= 100
void solve_sub2(int n, int k, vector<vector<ll>> &r, vector<vector<ll>> &u)
{
    vector<ll> p(k, 0);
    vector<bool> done(n, false);
    int ans = 0;
    while (true)
    {
        bool progress = false;
        for (int i = 0; i < n; i++)
        {
            if (done[i])
                continue;
            bool ok = true;
            for (int j = 0; j < k; j++)
            {
                if (p[j] < r[i][j])
                {
                    ok = false;
                    break;
                }
            }
            if (ok)
            {
                done[i] = true;
                for (int j = 0; j < k; j++)
                    p[j] += u[i][j];
                ans++;
                progress = true;
            }
        }
        if (!progress)
            break;
    }
    cout << ans << "\n";
}

// ======================= SUBTASK 3 =======================
// Greedy + heap cho k = 1
void solve_sub3(int n, int k, vector<vector<ll>> &r, vector<vector<ll>> &u)
{
    vector<pair<ll, ll>> a(n);
    for (int i = 0; i < n; i++)
    {
        a[i] = {r[i][0], u[i][0]};
    }
    sort(a.begin(), a.end()); // sort theo r[i]

    ll p = 0;
    int ans = 0;
    int idx = 0;
    priority_queue<ll> pq;

    while (true)
    {
        while (idx < n && a[idx].first <= p)
        {
            pq.push(a[idx].second);
            idx++;
        }
        if (pq.empty())
            break;
        ll gain = pq.top();
        pq.pop();
        p += gain;
        ans++;
    }
    cout << ans << "\n";
}

// ======================= SUBTASK 4 =======================
// Phiên bản chung (mô phỏng) - có thể chạy chậm với n, k rất lớn
void solve_sub4(int n, int k, vector<vector<ll>> &r, vector<vector<ll>> &u)
{
    vector<ll> p(k, 0);
    vector<bool> done(n, false);
    int ans = 0;

    while (true)
    {
        bool progress = false;
        for (int i = 0; i < n; i++)
        {
            if (done[i])
                continue;
            bool ok = true;
            for (int j = 0; j < k; j++)
            {
                if (p[j] < r[i][j])
                {
                    ok = false;
                    break;
                }
            }
            if (ok)
            {
                done[i] = true;
                for (int j = 0; j < k; j++)
                    p[j] += u[i][j];
                ans++;
                progress = true;
            }
        }
        if (!progress)
            break;
    }
    cout << ans << "\n";
}

// ======================= MAIN =======================
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    vector<vector<ll>> r(n, vector<ll>(k));
    vector<vector<ll>> u(n, vector<ll>(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];
    }

    // Chia subtask
    if (n == 1)
    {
        solve_sub1(n, k, r, u);
    }
    else if (n <= 100 && k <= 100)
    {
        solve_sub2(n, k, r, u);
    }
    else if (k == 1)
    {
        solve_sub3(n, k, r, u);
    }
    else
    {
        solve_sub4(n, k, r, u); // fallback
    }
    return 0;
}

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