Submission #692319

#TimeUsernameProblemLanguageResultExecution timeMemory
692319zeroesandonesMountains (IOI17_mountains)C++17
0 / 100
0 ms212 KiB
#include <bits/stdc++.h> #include "mountains.h" using namespace std; using ll = long long; using vi = vector<ll>; using pi = pair<ll, ll>; #define fr first #define sc second #define pb emplace_back bool check(pi a, pi b, pi c) { // check if c blocks a and b ll A = a.sc - b.sc; ll B = a.fr - b.fr; ll C = a.sc * (b.fr - a.fr) + a.fr * (a.sc - b.sc); return A * c.fr + B * c.sc + C > 0; } int maximum_deevs(vector<int> y) { int n = y.size(); int ans = 1; vector<pi> points(n); for(int i = 0; i < n; ++i) { points[i] = {i, y[i]}; } bool can_see[n][n] = {}; for(int i = 0; i < n; ++i) { for(int j = i + 1; j < n; ++j) { for(int k = i + 1; k < j; ++k) { if(check(points[i], points[j], points[k])) { can_see[i][j] = true; can_see[j][i] = true; } } } } for(int i = 0; i < (1<<n); ++i) { // check if subset is valid vi subset; for(int j = 0; j < n; ++j) { if(i & (1<<j)) subset.pb(j); } int m = subset.size(); bool valid = true; for(int j = 0; j < m - 1; ++j) { if(!can_see[subset[j]][subset[j + 1]]) { valid = false; break; } } if(valid) ans = max(ans, m); } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...