oj.uz

Submission #1039049

# Submission time Handle Problem Language Result Execution time Memory
1039049 2024-07-30T11:44:58 Z Shadow1 Topical (NOI23_topical) C++17
100 / 100
 405 ms 137964 KB 
// Programmer: Shadow1

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using str = string; // yay python!

#define i64 int64_t
#define watch(x) cerr << (#x) << " = " << (x) << '\n';
#define output_vector(v) for(auto &x : v){cout << x << " ";}cout << '\n';
#define vt vector
#define st stack
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define umap unordered_map
#define uset unordered_set
#define fir first
#define sec second
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()


// T: O(n^3)
// M : O(n + k log n)

void solve() {
	int n, k;
	cin >> n >> k;

	vector<vector<int>> r(n), u(n);
	vector<vector<pair<int,int>>> s(k);
	vector<int64_t> p(k);
	vector<int> c(n), ind(k,1);

	for(int i=0; i<n; ++i) {
		for(int j=0; j<k; ++j) {
			int x; cin >> x;
			r[i].push_back(x);
		}
	}
	for(int i=0; i<n; ++i) {
		for(int j=0; j<k; ++j) {
			int x; cin >> x;
			u[i].push_back(x);
		}
	}
	for(int j=0; j<k; ++j) {
		for(int i=0; i<n; ++i) {
			s[j].push_back({r[i][j],i});
			if(r[i][j] == 0) ++c[i];
		}
	}
	for(auto &S : s)
		sort(all(S));
	int ans = 0;
	bool one = 0;
	queue<int> q;
	for(int i=0; i<n; ++i) {
		if(c[i] == k) {
			one = 1;
			q.push(i);			
		} 
	}
	while(!q.empty()) {
		++ans;
		int cur = q.front();
		q.pop();
		for(int j=0; j<k; ++j) 
			p[j] += u[cur][j];

		for(int j=0; j<k; ++j) {
			for(int i=ind[j]; i<n; ++i) {
				if(s[j][i].fir <= p[j]) {
					++ind[j];
					++c[s[j][i].sec];
					if(c[s[j][i].sec] == k) 
						q.push(s[j][i].sec);
				} else
					break;
			}
		}
	}
	
	cout << ans << '\n';

}

int main() {
	// freopen("output.txt", "w", stdout);
	// freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(false);
	cin.tie(NULL); 
	
	solve();
	return 0;
}

/* CHECK :
1. COMPARATOR FUNCTION MUST RETURN FALSE WHEN ARGUMENTS ARE EQUAL!!!
2. Overflow! Typecase int64_t on operations if varaibles are int
3. Check array bounds!!!
4. Check array indexing!!!
5. Edge cases. (N==1)!!!
*/

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:62:7: warning: variable 'one' set but not used [-Wunused-but-set-variable]
   62 |  bool one = 0;
      |       ^~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 0 ms 352 KB Output is correct
3 Correct 2 ms 1120 KB Output is correct
4 Correct 165 ms 86220 KB Output is correct
5 Correct 175 ms 86336 KB Output is correct
6 Correct 181 ms 86332 KB Output is correct
7 Correct 140 ms 80504 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 356 KB Output is correct
4 Correct 0 ms 356 KB Output is correct
5 Correct 0 ms 356 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 2 ms 612 KB Output is correct
8 Correct 2 ms 612 KB Output is correct
9 Correct 2 ms 612 KB Output is correct
10 Correct 2 ms 736 KB Output is correct
11 Correct 2 ms 728 KB Output is correct
12 Correct 3 ms 1120 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 356 KB Output is correct
2 Correct 0 ms 356 KB Output is correct
3 Correct 3 ms 1892 KB Output is correct
4 Correct 31 ms 14292 KB Output is correct
5 Correct 33 ms 14068 KB Output is correct
6 Correct 405 ms 137964 KB Output is correct
7 Correct 381 ms 135624 KB Output is correct
8 Correct 398 ms 137912 KB Output is correct
9 Correct 366 ms 135648 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 0 ms 352 KB Output is correct
3 Correct 2 ms 1120 KB Output is correct
4 Correct 165 ms 86220 KB Output is correct
5 Correct 175 ms 86336 KB Output is correct
6 Correct 181 ms 86332 KB Output is correct
7 Correct 140 ms 80504 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 356 KB Output is correct
11 Correct 0 ms 356 KB Output is correct
12 Correct 0 ms 356 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 2 ms 612 KB Output is correct
15 Correct 2 ms 612 KB Output is correct
16 Correct 2 ms 612 KB Output is correct
17 Correct 2 ms 736 KB Output is correct
18 Correct 2 ms 728 KB Output is correct
19 Correct 3 ms 1120 KB Output is correct
20 Correct 0 ms 356 KB Output is correct
21 Correct 0 ms 356 KB Output is correct
22 Correct 3 ms 1892 KB Output is correct
23 Correct 31 ms 14292 KB Output is correct
24 Correct 33 ms 14068 KB Output is correct
25 Correct 405 ms 137964 KB Output is correct
26 Correct 381 ms 135624 KB Output is correct
27 Correct 398 ms 137912 KB Output is correct
28 Correct 366 ms 135648 KB Output is correct
29 Correct 177 ms 37724 KB Output is correct
30 Correct 181 ms 33672 KB Output is correct
31 Correct 248 ms 44664 KB Output is correct
32 Correct 140 ms 28396 KB Output is correct
33 Correct 166 ms 26616 KB Output is correct
34 Correct 178 ms 29180 KB Output is correct
35 Correct 221 ms 41348 KB Output is correct
36 Correct 181 ms 32340 KB Output is correct
37 Correct 196 ms 35060 KB Output is correct
38 Correct 156 ms 33512 KB Output is correct