Submission #747039

#TimeUsernameProblemLanguageResultExecution timeMemory
747039Doncho_BonbonchoMountains (IOI17_mountains)C++14
0 / 100
1 ms340 KiB
#include "mountains.h" #include <bits/stdc++.h> #include <cstdio> #include <vector> #include <cassert> typedef long long ll; const int MAX_N = 2048; const int INF = 1e9; ll dp[MAX_N][MAX_N]; struct Point{ int x, y; }; int signedArea( Point& a, Point& b ){ return ( a.x + b.y ) * ( a.y - b.x ); } int signedArea( Point& a, Point& b, Point& c ){ Point v1 = {b.x - a.x, b.y - a.y}; Point v2 = {c.x - a.x, c.y - a.y}; return signedArea( v1, v2 ); } bool cw( Point& a, Point& b, Point& c ){ return ( signedArea( a, b, c ) < 0 ); } Point p[MAX_N]; int maximum_deevs(std::vector<int> a){ int n = a.size(); std::reverse(a.begin(), a.end()); a.push_back(INF); std::reverse( a.begin(), a.end() ); n++; for( int i=1 ; i<n ; i++ ){ p[i] = {i, a[i]}; } for( int i=0 ; i<n ; i++ ){ dp[i][i] = 1ll; if( i ) dp[i-1][i] = 1; ll sum = 0; int last = i-1; // std::cerr<<i<<":\n"; for( int j=i-2; j>=0 ; j-- ){ // std::cerr<<" - "<<j<<"\n"; dp[j][i] = dp[j][i-1]; if( cw( p[i], p[last], p[j] ) ){ // std::cerr<<" new last \n"; sum += dp[j+1][last-1]; // std::cerr<<" + "<<dp[j+1][last-1]<<"\n"; last = j; } dp[j][i] = std::max( dp[j][i], sum + 1 ); // std::cerr<<" dp["<<j<<"]["<<i<<"] = "<<dp[j][i]<<"\n"; } } 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...