Submission #893317

#	Time	Username	Problem	Language	Result	Execution time	Memory
893317		vjudge1	Topical (NOI23_topical)	C++17	40 / 100	1074 ms	178700 KiB

Main

#include <bits/stdc++.h>
#define task ""
#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;
set <pii> s;

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)
        for (int j = 0;j < m;++j)
            cin >> a[i][j];
    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());
    }
    for (int i = 0;i < n;++i)
        s.insert({0, i}), cnt[i] = 0;
    while(!s.empty())
    {
        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;
                s.erase({cnt[ii], ii});
                cnt[ii]++;
                s.insert({cnt[ii], ii});
                l[j]++;
            }
        }
        auto it = *s.rbegin();
        if (it.ff != m) break;
        s.erase(it);
        int i = it.ss;
        for (int j = 0;j < m;++j)
            p[j] += b[i][j];
    }
    cout << n - (ll)s.size();
}

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