Submission #577959

#TimeUsernameProblemLanguageResultExecution timeMemory
577959perchutsMountains (IOI17_mountains)C++17
20 / 100
1 ms468 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 solve(int l,int r){//dp[l][r] => as pontas sao (l,r). if(pode[l][r]==0)return 0; if(dp[l][r])return dp[l][r]; int best = 2; for(int k=l+1;k<=r-1;++k){ if(pode[l][k]&&pode[k][r])ckmax(best,solve(l,k)+solve(k,r)-1); } return dp[l][r] = best; } 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]); } } ll ans = 1;//posso conseguir pegar so 1 for(int l=1;l<=n;++l){ for(int r=l+2;r<=n;++r){ ckmax(ans,solve(l,r)); } } return ans; } // int main(){ // int n;cin>>n; // vector<int>v(n); // for(auto&x :v)cin>>x; // cout<<maximum_deevs(v)<<endl; // }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...