Submission #970711

#TimeUsernameProblemLanguageResultExecution timeMemory
970711CSQ31Topical (NOI23_topical)C++17
100 / 100
483 ms163460 KiB
#include<bits/stdc++.h> using namespace std; #define pb push_back #define fi first #define se second #define sz(a) (int)(a.size()) #define all(a) a.begin(),a.end() #define lb lower_bound #define ub upper_bound #define owo ios_base::sync_with_stdio(0);cin.tie(0); #define MOD (ll)(998244353) #define INF (ll)(1e18) #define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr) #define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\ debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC)) typedef long long int ll; typedef long double ld; typedef pair<ll,ll> PII; typedef pair<int,int> pii; typedef vector<vector<int>> vii; typedef vector<vector<ll>> VII; const int MAXN = 1e6+1; vector<int>r[MAXN],u[MAXN]; vector<ll>p; vector<pii>ord[MAXN]; int cnt[MAXN],idx[MAXN]; int main() { owo int n,k; cin>>n>>k; p.assign(k,0); for(int i=0;i<n;i++){ cnt[i] = k; r[i].resize(k); for(int j=0;j<k;j++){ cin>>r[i][j]; ord[j].pb({r[i][j],i}); } } for(int i=0;i<n;i++){ u[i].resize(k); for(int j=0;j<k;j++)cin>>u[i][j]; } queue<int>q; for(int j=0;j<k;j++){ sort(all(ord[j])); idx[j] = -1; while(idx[j]+1 < n && ord[j][idx[j]+1].fi <= p[j]){ idx[j]++; int x = ord[j][idx[j]].se; cnt[x]--; if(!cnt[x])q.push(x); } } ll ans = 0; while(!q.empty()) { int v = q.front(); q.pop(); ans++; for(int j=0;j<k;j++)p[j] += u[v][j]; for(int j=0;j<k;j++){ while(idx[j]+1 < n && ord[j][idx[j]+1].fi <= p[j]){ idx[j]++; int x = ord[j][idx[j]].se; cnt[x]--; if(!cnt[x])q.push(x); } } } cout<<ans<<'\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...