Submission #867997

#	Time	Username	Problem	Language	Result	Execution time	Memory
867997		12345678	Money (IZhO17_money)	C++17	100 / 100	862 ms	61956 KiB

money

#include <bits/stdc++.h>

using namespace std;

const int inf=1e9, nx=1e6+5;
int n, v[nx], l, idx, dp[nx];
set<int> s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    s.insert(1e9);
    for (int i=1; i<=n; i++)
    {
        cin>>v[i];
        //cout<<i<<' '<<v[i]<<' '<<l<<'\n';
        if (v[i]>=v[i-1]&&v[i]<=l) 
        {
            dp[i]=dp[idx]+1;
        }
        else
        {
            while (idx<i) s.insert(v[idx]), idx++;
            l=*s.upper_bound(v[i]);
            idx=i-1;
            dp[i]=dp[i-1]+1;
        }
        //cout<<"here"<<' '<<dp[i]<<'\n';
    }
    cout<<dp[n];
}

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