1572E - Polygon - CodeForces Solution

#include <iostream>
using namespace std;
const int N=205;
long long n,k,x[N],y[N];
pair<long long,long long> f[N][N];
long long area(long long i,long long j,long long k) {
  return (x[j]-x[i])*(y[k]-y[i])-(y[j]-y[i])*(x[k]-x[i]);
}
int main(){
  cin>>n>>k;
  for(int i=1;i<=n; i++) cin>>x[i]>>y[i];
  long long l=0,r=1e17;
  while(l<r){
    long long mid=(l+r+1)>>1;
    for(long long len=3;len<=n;len++){
      for(long long i=1,j=len;j<=n;i++,j++){
        f[i][j]={0,0};
        for(long long k=i+1;k<j;k++){
          long long a=f[i][k].first+f[k][j].first;
          long long b=f[i][k].second+f[k][j].second+area(i,k,j);
          f[i][j]=max(f[i][j],b>=mid?make_pair(a+1,0ll):make_pair(a,b));
        }
      }
    }
    f[1][n].first> k?l=mid:r=mid-1;
  }
  cout<<l<<endl;
  return 0;
}