Submission #577960

#TimeUsernameProblemLanguageResultExecution timeMemory
577960perchutsMountains (IOI17_mountains)C++17
100 / 100
40 ms18100 KiB
#include <bits/stdc++.h> #define all(x) x.begin(), x.end() #define sz(x) (int) x.size() #define endl '\n' #define pb push_back #define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); using namespace std; using ll = long long; using ull = unsigned long long; using ii = pair<int,int>; using iii = tuple<int,int,int>; const int inf = 2e9+1; const int mod = 1e9+7; const int maxn = 1e5+100; template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; } template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; } int dp[2001][2001], y[2001]; bool pode[2001][2001]; int maximum_deevs(vector<int>v){ int n = sz(v); for(int i=0;i<n;++i){ y[i+1] = v[i]; ll bx = 0, by = 0; for(int j=i+1;j<n;++j){ if(bx*ll(v[j]-v[i])<by*ll(j-i))pode[i+1][j+1] = 1; else bx = ll(j-i), by = ll(v[j]-v[i]); } } for(int r=1;r<=n;++r){ dp[r][r] = 1; int sum = 0, last = r; for(int l=r-1;l>=1;--l){ dp[l][r] = dp[l][r-1]; if(pode[l][r]==0){ sum += dp[l+1][last-1], last = l; } ckmax(dp[l][r], sum + 1 + dp[l][last-1]); } } return dp[1][n]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...