D. Discrete Centrifugal Jumps SOLUTIONS Codeforces Round #669 (Div. 2)

Discrete Centrifugal Jumps SOLUTION

There are n lovely high rises in New York, the stature of the I-th one is hey. Today a few miscreants have set ablaze first n−1 of them, and now the main security building is n-th high rise.
How about we call a bounce from I-th high rise to j-th (i<j) discrete, if all high rises between are carefully lower or higher than them two. Officially, hop is discrete, if i<j and one of the accompanying conditions fulfilled:
i+1=j
max(hi+1,… ,hj−1)<min(hi,hj)
max(hi,hj)<min(hi+1,… ,hj−1).
Right now, Vasya is remaining on the primary high rise and needs to live somewhat more, so he will likely arrive at n-th high rise with negligible check of discrete hops. Help him with calcualting this number.
Info
The main line contains a solitary whole number n (2≤n≤3⋅105) — aggregate sum of high rises.
The subsequent line contains n numbers h1,h2,… ,hn (1≤hi≤109) — statures of high rises.
Yield
Print single number k — negligible measure of discrete hops. We can show that an answer consistently exists.
Models
inputCopy
5
1 3 1 4 5
outputCopy
3
inputCopy
4
4 2 4
outputCopy
1
inputCopy
2
1
outputCopy
1
inputCopy
5
100 1 100 1 100
outputCopy
2
Note
In the first testcase, Vasya can hop in the accompanying way: 1→2→4→5.
In the second and third testcases, we can arrive at last high rise in one hop.
Grouping of hops in the fourth testcase: 1→3→5.

1 thought on “D. Discrete Centrifugal Jumps SOLUTIONS Codeforces Round #669 (Div. 2)”

  1. #include
    using namespace std;

    #define int long long
    #define ld long double
    #define fi first
    #define se second
    #define pb push_back
    #define mp make_pair
    #define fo(i,n) for(i=0;i=0;i–)
    #define of1(i,n) for(i=n;i>=1;i–)
    #define ofab(i,a,b) for(i=a;i>=b;i–)
    #define sq(a) (a)*(a)
    #define all(x) x.begin(),x.end()
    #define rall(x) x.rbegin(),x.rend()
    #define sortall(x) sort(all(x))
    #define sortrall(x) sort(rall(x))
    #define clr(x) memset(x,0,sizeof(x))
    #define tr(it, a) for(auto it=a.begin();it!=a.end();it++)
    #define pii pair
    #define mk(arr,n,type) type *arr=new type[n];
    #define vi vector
    #define vpii vector
    #define si set
    #define spii set
    #define usi unordered_set
    #define uspii unordered_set
    #define mii map
    #define umii unordered_map
    #define pqmx priority_queue
    #define pqmn priority_queue>
    #define setbits(x) __builtin_popcountll(x)
    #define trailzrobits(x) __builtin_ctzll(x)
    #define leadzrobits(x) __builtin_clzll(x)
    #define paritybits(x) __builtin_parityll(x)
    #define gcd __gcd
    #define lcm(x, y) (x*y)/gcd(x,y)
    #define endl 'n'
    #define sz(s) (int)s.size()
    #define sp(x,y) fixed< void __print(const pair &x) {cout<<'{';__print(x.first);cout<<',';__print(x.second);cout<<'}';}
    template void __print(const T &x) {int f=0;cout<<'{';for(auto &i:x)cout<<(f++?",":""),__print(i);cout<<"}";}void _print(){cout<<"]n";}
    template void _print(T t, V… v) {__print(t);if(sizeof…(v))cout<<", ";_print(v…);}
    #ifndef ONLINE_JUDGE
    #define dbg(x…) cout<<"["<<#x<<"]=[";_print(x)
    #else
    #define dbg(x…)
    #endif
    int powerm(int base,int exp) {int res=1;base%=mod;while(exp>0){if(exp&1)res=(res*base)%mod;base=(base*base)%mod;exp=exp>>1;}return res;}
    int power(int base,int exp) {int res=1;while(exp>0){if(exp&1)res=res*base;base=base*base;exp=exp>>1;}return res;}
    float powerNeg(float base,int exp) {float temp;if(exp==0)return 1;temp=powerNeg(base,exp/2);if(exp%2==0)return temp*temp;else{if(exp>0)return base*temp*temp;else return (temp*temp)/base;}}
    int modinv(int exp) {return powerm(exp,mod-2);}
    // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

    const int N=1e3+5,M=N;
    int dp[N][N];
    bool rec(vi &a,int i,int k){

    if(k==0) return 1;
    if(i==a.size()) return 0;

    if(dp[i][k]!=-1) return dp[i][k];

    bool ok=0;
    if(k>=a[i]) ok=rec(a,i+1,k-a[i]);
    return dp[i][k]=(ok | rec(a,i+1,k));
    }
    void solve(){

    int i,j,k;
    int n; cin>>k>>n;
    vi a(n); fo(i,n) cin>>a[i];

    memset(dp,-1,sizeof(dp));
    cout<>T;
    fo1(t,T){
    // cout<<"Case #"<<t<<": ";
    solve();
    }
    // cout<<endl<<"Times Elapsed:"<<1.0*clock()/CLOCKS_PER_SEC<<"sec";
    return 0;
    }

    Reply

Leave a Comment

close
error: Content is protected !!
Free Udemy Courses and Hacking Resources Join Us on TelegramClick Here
+