Submission #734572

#TimeUsernameProblemLanguageResultExecution timeMemory
734572abcvuitunggioMountains (IOI17_mountains)C++17
0 / 100
9 ms16004 KiB
#include "mountains.h" #include <bits/stdc++.h> 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); } int 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 (stderr)

mountains.cpp: In function 'int f(int, int)':
mountains.cpp:23:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for (int k=0;k<v[j].size()-1;k++)
      |                  ~^~~~~~~~~~~~~~
mountains.cpp: In function 'int maximum_deevs(std::vector<int>)':
mountains.cpp:28:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for (int i=1;i<=y.size();i++){
      |                  ~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...