思路
有一个很简单的 \(\Theta(n^2m)\) 的做法,每一轮枚举所有未进行的考核,判断以当前的能力能否通过这个考核,然后更新当前的能力。
考虑优化,如果每一次都能精准找到一个能够通过的考核,那么就能优化掉一个 \(n\)。对于每一场考核的对元素 \(i\) 的要求从小到大排序,那么以当前元素 \(i\) 的掌控力一定是这个序列的一个前缀。
那么每一轮枚举每一个元素,更新对于每一个元素能满足要求的前缀位置,然后更新每一场考核已经有多少种元素满足要求即可。
因为每一轮都会至少完成一场考核,所以复杂度是 \(\Theta(nm \log m)\) 的,瓶颈在于排序。
Code
#include <bits/stdc++.h>
#define re register
#define fst first
#define snd second
#define int long longusing namespace std;typedef pair<int,int> pii;
const int N = 1e6 + 10;
int n,m,ans;
int p[N],sum[N];
vector<pii> v[N];
vector<vector<int>> arr,w;inline int read(){int r = 0,w = 1;char c = getchar();while (c < '0' || c > '9'){if (c == '-') w = -1;c = getchar();}while (c >= '0' && c <= '9'){r = (r << 3) + (r << 1) + (c ^ 48);c = getchar();}return r * w;
}signed main(){n = read(),m = read();arr.resize(n + 5); w.resize(n + 5);for (re int i = 0;i <= n + 2;i++){ w[i].resize(m + 5); arr[i].resize(m + 5); }for (re int i = 1;i <= n;i++){for (re int j = 1;j <= m;j++) v[j].push_back({arr[i][j] = read(),i});}for (re int i = 1;i <= n;i++){for (re int j = 1;j <= m;j++) w[i][j] = read();}for (re int i = 1;i <= m;i++) sort(v[i].begin(),v[i].end(),[](const pii &a,const pii &b){ return a > b; });while (1){bool falg = false;for (re int i = 1;i <= m;i++){while (!v[i].empty() && v[i].back().fst <= p[i]){int id = v[i].back().snd;if ((++sum[id]) == m){falg = true;for (re int j = 1;j <= m;j++) p[j] += w[id][j];} v[i].pop_back();}}if (!falg) break;}for (re int i = 1;i <= n;i++) ans += (sum[i] == m);printf("%d",ans);return 0;
}