제출 #893329

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
893329		NgTrung2217	Topical (NOI23_topical)	C++14	100 / 100	390 ms	143336 KiB

Main

#include <bits/stdc++.h>
#define task "60131A"
#define ff first
#define ss second
using namespace std;
using ld = long double;
using ull = unsigned long long;
using ll = long long;
using pll = pair <ll, ll>;
using pii = pair <int, int>;
const char el = '\n';
const char sp = ' ';
const ll inf = 1e9; //1e18;
const ll maxN = 1e6 + 1;
int n, m;
int l[maxN], cnt[maxN];
ll p[maxN];
vector <vector <ll>> a, b;
vector <vector <pll>> c;
deque <int> dq;

int main ()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    freopen(task".inp", "r", stdin);
//    freopen(task".out", "w", stdout);
    cin >> n >> m;
    a.resize(n, vector <ll> (m));
    b.resize(n, vector <ll> (m));
    for (int i = 0;i < n;++i)
    {
        bool ok = 1;
        for (int j = 0;j < m;++j)
        {
            cin >> a[i][j];
            ok &= (a[i][j] == 0);
        }
        if (ok) dq.push_back(i), cnt[i] = inf;
    }
    for (int i = 0;i < n;++i)
        for (int j = 0;j < m;++j)
            cin >> b[i][j];
    c.resize(m, vector <pll> (n));
    for (int j = 0;j < m;++j)
    {
        l[j] = 0;
        for (int i = 0;i < n;++i)
            c[j][i] = {a[i][j], i};
        sort(c[j].begin(), c[j].end());
    }
    int ans = 0;
    while(!dq.empty())
    {
        auto it = dq.front();
        ans++;
        dq.pop_front();
        int i = it;
        for (int j = 0;j < m;++j)
            p[j] += b[i][j];
        for (int j = 0;j < m;++j)
        {
            while(l[j] < n && c[j][l[j]].ff <= p[j])
            {
                int ii = c[j][l[j]].ss;
                cnt[ii]++;
                if (cnt[ii] == m) dq.push_back(ii);
                l[j]++;
            }
        }
    }
    cout << ans;
}

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