Submission #795305

#TimeUsernameProblemLanguageResultExecution timeMemory
795305vjudge1Team Contest (JOI22_team)C++14
18 / 100
150 ms125956 KiB
#include<bits/stdc++.h> #define fi first #define se second using namespace std ; const int N = 15e4 ; bool flag1, flag2, flag3 ; int n, ans = -1, x[N + 1], y[N + 1], z[N + 1] ; set<pair<int, pair<int, int>>> s ; vector<pair<int, pair<int, int>>> v ; int func(int i, int j, int q) { if(x[i] > x[j] && x[i] > x[q] && y[j] > y[i] && y[j] > y[q] && z[i] < z[q] && z[j] < z[q]) return x[i] + y[j] + z[q] ; else return -1 ; } int func1(int i, int j, int q) { if(v[i].fi > v[j].fi && v[i].fi > v[q].fi && v[j].se.fi > v[i].se.fi && v[j].se.fi > v[q].se.fi && v[i].se.se < v[q].se.se && v[j].se.se < v[q].se.se) return v[i].fi + v[j].se.fi + v[q].se.se ; else return -1 ; } signed main() { ios_base::sync_with_stdio( 0 ) ; cin.tie( 0 ) ; cout.tie( 0 ) ; cin >> n ; for(int i = 1 ; i <= n ; i++) { cin >> x[i] >> y[i] >> z[i] ; if(x[i] > 5 || y[i] > 5 || z[i] > 5)flag1 = 1 ; if(x[i] > 20 || y[i] > 20 || z[i] > 20)flag2 = 1 ; if(x[i] > 4000 || y[i] > 4000 || z[i] > 4000)flag3 = 1 ; s.insert({x[i], {y[i], z[i]}}) ; } if(n <= 4000) { set<int> s ; int mx[n + 1][n + 1] = {}, num[n + 1][n + 1] = {}, kol = 0 ; map<int, int> mp, ob ; for(int i = 1 ; i <= n ; i++) { s.insert(x[i]) ; s.insert(y[i]) ; } for(int i : s) kol++, mp[i] = kol ; for(int i = 1 ; i <= n ; i++) { ob[mp[x[i]]] = x[i] ; ob[mp[y[i]]] = y[i] ; x[i] = mp[x[i]] ; y[i] = mp[y[i]] ; num[x[i]][y[i]] = z[i] ; } for(int i = 1 ; i <= n ; i++) { int now = 0 ; for(int j = 1 ; j <= n ; j++) { now = max(now, num[i][j]) ; mx[i][j] = max(now, mx[i - 1][j]) ; } } // for(int i = 1 ; i <= n ; i++) // { // for(int j = 1 ; j <= n ; j++) // cout << num[i][j] << ' ' ; // cout << '\n' ; // } for(int i = 1 ; i <= n ; i++) for(int j = 1 ; j <= n ; j++) { if(i == j || x[i] <= x[j] || y[j] <= y[i] || mx[x[i] - 1][y[j] - 1] <= max(z[i], z[j])) continue ; ans = max(ans, ob[x[i]] + ob[y[j]] + mx[x[i] - 1][y[j] - 1]) ; } cout << ans << '\n' ; return 0 ; } if(!flag3) { } if(!flag2) { for(auto i : s) v.push_back(i) ; for(int i = 1 ; i <= 20 ; i++) for(int j = 1 ; j <= 20 ; j++) for(int q = 1 ; q <= 20 ; q++) { bool fl1 = 0, fl2 = 0, fl3 = 0 ; for(auto now : v) { if(now.fi == i && now.se.fi < j && now.se.se < q)fl1 = 1 ; if(now.fi < i && now.se.fi == j && now.se.se < q)fl2 = 1 ; if(now.fi < i && now.se.fi < j && now.se.se == q)fl3 = 1 ; } if(fl1 && fl2 && fl3) ans = max(ans, i + j + q) ; } cout << ans ; return 0 ; } if(n <= 300) { for(int i = 1 ; i <= n ; i++) for(int j = 1 ; j <= n ; j++) { if(i == j) continue ; for(int q = 1 ; q <= n ; q++) { if(j == q || i == q) continue ; ans = max(ans, func(i, j, q)) ; } } cout << ans << '\n' ; return 0 ; } return 0 ; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...