Submission #1126618

#TimeUsernameProblemLanguageResultExecution timeMemory
1126618brover29Money (IZhO17_money)C++20
25 / 100
1596 ms328 KiB
#include <bits/stdc++.h> //qwerty47924692 using namespace std; using ll = long long; const ll N=2e5+29; const string br="617283"; ll n,a[N],ans=1e18; vector<vector<ll>>cur; void f(ll x){ if(x==n){ ll cnt=0; set<ll>s; for(ll i=0;i<cur.size();i++){ ll mn=cur[i].front(); ll mx=cur[i].back(); auto it=s.lower_bound(mx); if(it==s.begin()){ goto can; } --it; if(mn<*it){ return; } can:; for(ll i:cur[i]){ s.insert(i); } } ans=min(ans,(ll)cur.size()); return; } x++; if(a[x]>=a[x-1]){ cur[cur.size()-1].push_back(a[x]); f(x); cur[cur.size()-1].pop_back(); } cur.push_back({a[x]}); f(x); cur.pop_back(); } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin>>n; for(ll i=1;i<=n;i++)cin>>a[i]; cur.push_back({}); f(0); cout<<ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...