Submission #1016607

#TimeUsernameProblemLanguageResultExecution timeMemory
1016607ByeWorldTopical (NOI23_topical)C++14
100 / 100
612 ms148500 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3", "unroll-loops") #define ll long long #define int long long #define pb push_back #define fi first #define se second #define lf (id<<1) #define rg ((id<<1)|1) #define md ((l+r)>>1) #define ld long double using namespace std; typedef pair<int,int> pii; typedef pair<pii, int> ipii; const int MAXN = 5e5+10; const int MAXA = 2e3+10; const int INF = 1e18+10; const int LOG = 19; const int MOD = 1e9+7; const int SQRT = 450; const vector<int> NOL = {}; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const vector<int> dx = {1, -1, 0, 0}; const vector<int> dy = {0, 0, 1, -1}; void chmx(int &a, int b){ a = max(a, b); } int n, k; signed main(){ // ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n >> k; vector <int> te(k+1, 0); vector <vector<int>> u(n+1, te), r(n+1, te); vector <int> nw(k+1, 0); vector <int> done(n+1, 0); vector<pii>pp; vector<vector<pii>> vec(k+1, pp); for(int i=1; i<=n; i++){ for(int j=1; j<=k; j++){ cin >> r[i][j]; vec[j].pb({r[i][j], i}); } } for(int j=1; j<=k; j++) sort(vec[j].rbegin(), vec[j].rend()); for(int i=1; i<=n; i++){ for(int j=1; j<=k; j++){ cin >> u[i][j]; } } bool can = 1; int ANS = 0; while(can){ can = 0; // cout << " pp\n"; for(int j=1; j<=k; j++){ while(!vec[j].empty() && vec[j].back().fi <= nw[j]){ int idx = vec[j].back().se; done[idx]++; if(done[idx] == k){ can = 1; ANS++; for(int p=1; p<=k; p++) nw[p] += u[idx][p]; } vec[j].pop_back(); } } } 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...