Submission #692296

#TimeUsernameProblemLanguageResultExecution timeMemory
692296zeroesandonesMountains (IOI17_mountains)C++17
0 / 100
0 ms212 KiB
#include <bits/stdc++.h> #include "mountains.h" using namespace std; using ll = long long; using ld = long double; using vi = vector<ll>; bool check(int x, int y, int a, int b, int _a, int _b) { ld A = (ld) (a - _a); ld B = (ld) (_b - b); ld C = (ld) (b * (_a - a) + a * (b - _b)); ld res = A * y + B * x + C; return res > 0; } int maximum_deevs(vector<int> y) { int n = y.size(); int ans = 1; for(int i = 0; i < (1<<n); ++i) { vi subset; for(int j = 0; j < n; ++j) { if(i & (1<<j)) subset.emplace_back(j); } bool valid = true; int m = subset.size(); sort(subset.begin(), subset.end()); for(int j = 0; j < m - 1; ++j) { bool bigger = false; for(int x = subset[j] + 1; x < subset[j + 1]; ++x) { if(check(x, y[x], subset[j], y[subset[j]], subset[j + 1], y[subset[j + 1]])) { bigger = true; break; } } if(!bigger) { 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...