This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "mountains.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using pl = pair<long long, long long>;
using vi = vector<int>;
using vl = vector<long long>;
using vpi = vector<pair<int, int>>;
using vpl = vector<pair<long long, long long>>;
#define fur(i, a, b) for(ll i = a; i <= (ll)b; ++i)
#define ruf(i, a, b) for(ll i = a; i >= (ll)b; --i)
#define fr first
#define sc second
#define mp make_pair
#define pb emplace_back
#define nl "\n"
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
bool check(vector<int> &y, int i, int j, int k) {
int A = y[i] - y[j];
int B = i - j;
int C = y[i] * (j - i) + i * (y[i] - y[j]);
return A*k + B*y[k] + C > 0;
}
int check_bit(int bit, vector<int> &y, int n) {
int ans = 0;
bool d[n] = {};
for(int i = 0; i < n; ++i) {
if(bit & (1 << i)) {
d[i] = 1;
++ans;
}
}
for(int i = 0; i < n; ++i) {
if(!d[i])
continue;
for(int j = i + 1; j < n; ++j) {
if(!d[j])
continue;
bool block = 0;
for(int k = i + 1; k <= j - 1; ++k) {
if(check(y, i, j, k))
block = 1;
}
if(!block)
return 0;
}
}
return ans;
}
int maximum_deevs(vector<int> y) {
int ans = 1;
int n = y.size();
for(int b = 0; b < (1 << n); ++b) {
ans = max(ans, check_bit(b, y, n));
}
return ans;
// bool ok[n][n] = {};
// for(int i = 0; i < n; ++i) {
// for(int j = i + 2; j < n; ++j) {
// for(int k = i + 1; k < j; ++k) {
// ok[i][j] = check(y, i, j, k);
// }
// }
// }
// int dp[n] = {};
// dp[n] = 1;
// for(int i = n - 1; i >= 0; --i) {
// dp[i] = 1;
// for(int j = i + 2; j < n; ++j) {
// if(ok[i][j]) {
// dp[i] = max(dp[i], dp[j] + 1);
// }
// }
// ans = max(ans, dp[i]);
// }
// return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |