Submission #1259711

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259711		phtung	Topical (NOI23_topical)	C++20	12 / 100	104 ms	47432 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define name "IO"
#define int long long 

const int inf = 1e18 + 7; 
const int maxn = 1e6 + 5;
int n, k; 
vector<vector<int>> r, u;

void sub1()
{
    for(int j = 1; j <= k; j++)
    {
        if(r[1][j] > 0)
        {
            cout << 0 << "\n";
            return; 
        }
    }

    cout << 1 << "\n"; 
}

void sub3()
{
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq; 
    for(int i = 1; i <= n; i++)
    {   
        pq.push({r[i][1], i}); 
    }

    int cur = 0, res = 0;

    while(!pq.empty())
    {
        auto [val, id] = pq.top();
        pq.pop(); 

        if(cur >= val)
        {
            res++; 
            val += u[id][1]; 
        }
    }

    cout << res << "\n"; 
}

void sub2()
{
    int res = 0;
    vector<int> cur(k + 1, 0), vis(n + 1, 0); 

    while(true)
    {
        int cnt = 0; 

        for(int i = 1; i <= n; i++)
        {
            if(vis[i]) continue; 
            bool ok = 1; 
            for(int j = 1; j <= k; j++)
            {
                if(cur[j] < r[i][j]) 
                {
                    ok = 0;
                    break; 
                }
            }

            if(ok)
            {
                cnt++; 
                for(int j = 1; j <= k; j++) cur[j] += u[i][j]; 
                vis[i] = 1; 
            }
        }

        if(!cnt) break; 

        res += cnt; 
    }

    cout << res << "\n"; 
}
void solve()
{
    cin >> n >> k;

    r.resize(n + 1, vector<int>(k + 1)), u.resize(n + 1, vector<int>(k + 1)); 

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= k; j++)
        {
            cin >> r[i][j]; 
        }
    }

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= k; j++)
        {
            cin >> u[i][j];
        }
    }

    if(n == 1) sub1(); 

    else if(k == 1) sub3(); 

    else if(n <= 100) sub2(); 

}

signed main()
{
    if (fopen (name".INP", "r"))
    {
        freopen (name".INP", "r", stdin);
        freopen (name".OUT", "w", stdout);
    }

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    clock_t start = clock(); 

    int t = 1;

    while(t--) solve(); 

    std::cerr << "Time: " << clock() - start << "ms\n";

    return 0; 

}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:123:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |         freopen (name".INP", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:124:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |         freopen (name".OUT", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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