#include <bits/stdc++.h>
using namespace std;
#define HOME
#ifndef HOME
#include "mountains.h"
#endif // HOME
using ll = long long;
struct point_t {
int x;
int y;
};
/**
6
6 1 5 2 3 1
**/
const int MAX_N = 2000;
point_t p[1 + MAX_N];
int dp[1 + MAX_N][1 + MAX_N];
ll area (point_t a, point_t b, point_t c) {
return 1ll * a.x * a.y + 1ll * b.x * c.y + 1ll * c.x * a.y - 1ll * a.y * c.x - 1ll * b.y * a.x - 1ll * c.y * b.x;
}
int maximum_deevs(std::vector<int> y) {
int n = y.size ();
for (int i = 1; i <= n; i++)
p[i] = {i, y[i - 1]};
for (int i = 1; i <= n; i++) {
int k = i; dp[i][i] = 1;
int offset = 0;
for (int j = i - 1; j > 0; j--) {
dp[j][i] = dp[j + 1][i];
if (area (p[j], p[k], p[i]) >= 0)
offset += dp[j + 1][k - 1], k = j;
dp[j][i] = max (dp[j][i], 1 + offset + dp[j][k - 1]);
}
}
return dp[1][n];
}
#ifdef HOME
int main() {
int n;
assert(1 == scanf("%d", &n));
std::vector<int> y(n);
for (int i = 0; i < n; i++) {
assert(1 == scanf("%d", &y[i]));
}
int result = maximum_deevs(y);
printf("%d\n", result);
return 0;
}
#endif // HOME
Compilation message
/tmp/ccLrQGj5.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccL4aPKt.o:mountains.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
