제출 #1126618

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1126618		brover29	Money (IZhO17_money)	C++20	25 / 100	1596 ms	328 KiB

money

#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;
}

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 0 / 20
• Subtask 4: 0 / 55