Submission #652426

#TimeUsernameProblemLanguageResultExecution timeMemory
652426JooDdaeMountains (IOI17_mountains)C++17
0 / 100
1 ms212 KiB
#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({i, y[i-1]}, {k, y[k-1]}, {j, y[j-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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...