Submission #905288

#TimeUsernameProblemLanguageResultExecution timeMemory
905288rainboyMountains (IOI17_mountains)C++17
100 / 100
10 ms16216 KiB
#include "mountains.h" #include <vector> using namespace std; typedef vector<int> vi; const int N = 2000; int max(int a, int b) { return a > b ? a : b; } long long cross(int x0, int y0, int x1, int y1, int x2, int y2) { return (long long) (x1 - x0) * (y2 - y0) - (long long) (x2 - x0) * (y1 - y0); } int dp[N][N]; int maximum_deevs(vi yy) { int n = yy.size(); for (int i = n - 1; i >= 0; i--) { dp[i][i] = 1; int k = i, x = 0; for (int j = i + 1; j < n; j++) { dp[i][j] = dp[i + 1][j]; if (cross(i, yy[i], k, yy[k], j, yy[j]) >= 0) { if (j - k > 1) x += dp[k + 1][j - 1]; k = j; dp[i][j] = max(dp[i][j], x + 1); } else dp[i][j] = max(dp[i][j], x + dp[k + 1][j] + 1); } } return dp[0][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...