#include "mountains.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct point{
int x,y;
}p[2001];
inline point operator-(point a, point b){
return {a.x-b.x,a.y-b.y};
}
inline int operator*(point a, point b){
return a.x*b.y-a.y*b.x;
}
int dp[2001][2001];
vector <int> v[2001];
int f(int i, int j){
if (i==j)
return 1;
if (i>j)
return 0;
if (dp[i][j]!=-1)
return dp[i][j];
int res=1;
for (int k=0;k<v[j].size()-1;k++)
res+=f(max(v[j][k]+1,i),v[j][k+1]-1);
return dp[i][j]=max(f(i,j-1),res);
}
int32_t maximum_deevs(vector <int> y){
for (int i=1;i<=y.size();i++){
v[i].push_back(0);
p[i]={i,y[i-1]};
for (int j=1;j<i;j++){
while (v[i].size()>1&&(p[j]-p[i])*(p[v[i].back()]-p[i])>0)
v[i].pop_back();
v[i].push_back(j);
}
}
memset(dp,-1,sizeof(dp));
return f(1,y.size());
}
Compilation message
mountains.cpp: In function 'long long int f(long long int, long long int)':
mountains.cpp:24:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | for (int k=0;k<v[j].size()-1;k++)
| ~^~~~~~~~~~~~~~
mountains.cpp: In function 'int32_t maximum_deevs(std::vector<long long int>)':
mountains.cpp:29:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for (int i=1;i<=y.size();i++){
| ~^~~~~~~~~~
/usr/bin/ld: /tmp/cctWADY4.o: in function `main':
grader.cpp:(.text.startup+0x238): undefined reference to `maximum_deevs(std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status
