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;
struct point{
ll x, y;
bool operator < (const point &a)const{
return tie(x, y) < tie(a.x, a.y);
}
bool operator <= (const point &a)const{
return tie(x, y) <= tie(a.x, a.y);
}
point operator - (const point &a)const{
return {x-a.x, y-a.y};
}
bool operator == (const point &a)const{
return tie(x, y) == tie(a.x, a.y);
}
};
ll cross(point a, point b){
return a.x * b.y - a.y * b.x;
}
int ccw(point a, point b, point c){
ll re = cross(b-a, c-a);
return re > 0 ? 1 : re < 0 ? -1 : 0;
}
int dp[2020][2020];
int maximum_deevs(vector<int> y) {
int n = y.size();
for(int i=1;i<=n;i++) {
dp[i][i] = dp[i][i-1] = 1;
for(int j=i-2, k=i-1, s=1;j>=1;j--) {
if(ccw({j, y[j-1]}, {k, y[k-1]}, {i, y[i-1]}) >= 0) {
s += dp[k-1][j+1], k = j;
} else {
dp[i][j] += dp[k-1][j];
}
dp[i][j] += s;
}
}
return dp[n][1];
}
# | 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... |