Submission #886289

#TimeUsernameProblemLanguageResultExecution timeMemory
886289Hovhannes1234Money (IZhO17_money)C++17
0 / 100
2 ms8280 KiB
#include <bits/stdc++.h> using namespace std; const int N=1e6+10; vector <int> a(N), dp(N); int main() { int n; cin>>n; for(int i=1; i<=n; i++) cin>>a[i]; dp[0] = 0; dp[1] = 1; for(int i=2; i<=n; i++)dp[i]=1e7; for(int i=2; i<=n; i++){ for(int j=1; j<=i; j++){ bool flag = true; for(int k=j; k<i; k++){ if(a[k] > a[k+1]){ flag = false; break; } } if(!flag)continue; int upper_j = upper_bound(a.begin(), a.end(), a[j])-a.begin(); if(a[upper_j] > a[j] && a[upper_j] < a[i]){ flag = false; break; } if(!flag)continue; dp[i] = min(dp[i], dp[j-1] + 1); //cout<<j<<" "<<i<<endl; } } cout<<dp[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...