1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84
| #include <bits/stdc++.h>
#pragma optimization_level 3 #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx") #pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") #pragma GCC optimization ("unroll-loops")
#define MAX_N 202 #define ll long long #define pll pair<ll, ll> #define vpll vector<pll> #define vall3 vector<array<ll,3>> #define vll vector<ll> #define vs vector<string> #define vvs vector<vs> #define vvll vector<vll> #define all(a) begin(a), end(a) using namespace std;
ll n; vll adj[MAX_N]; ll seen[MAX_N], match[MAX_N];
bool eat(array<ll,3>& a, array<ll,3>& b) { return a[0] >= b[0] and a[1] >= b[1] and a[2] >= b[2]; }
bool eq(array<ll,3>& a, array<ll,3>& b) { return a[0] == b[0] and a[1] == b[1] and a[2] == b[2]; }
bool dfs(ll u, ll s) { seen[u] = s; for(auto& v : adj[u]) { if(match[v] == -1 or (seen[match[v]] != s and dfs(match[v], s))) { match[v] = u; return true; } } return false; }
ll solve(vall3& spec) { ll u = 52, v = 53, gap = 100; for(ll i = 0; i < n; i++) { for(ll j = 0; j < n; j++) { if((eq(spec[i], spec[j]) and i < j) or (!eq(spec[i], spec[j]) and eat(spec[i], spec[j]))) { adj[i].push_back(j + gap); } } } ll res = 0; memset(seen, -1, sizeof seen); memset(match, -1, sizeof match); for(ll i = 0; i < n; i++) { dfs(i, i * 2); dfs(i, i * 2 + 1); }
for(ll i = 0; i < n; i++) { res += match[i + gap] == -1; }
return res; }
int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.setf(ios::fixed); cout.precision(6); cin>>n; vall3 sh; for(ll i = 0, s, p, c; i < n; i++) { cin>>s>>p>>c; sh.push_back({s,p,c}); }
cout<<solve(sh);
return 0; }
|