Submission #114798

#	Time	Username	Problem	Language	Result	Execution time	Memory
114798		MohamedAhmed04	Mountains (IOI17_mountains)	C++14	100 / 100	35 ms	16384 KiB

mountains

#include "mountains.h"
#include <bits/stdc++.h>

using namespace std ;

const int MAX = 2005 ;
int dp[MAX][MAX] ;
int n ;
vector<int>v ;

/*long double slope(int a , int b , int a2 , int b2)
{
    long double x = a * 1.0000 ;
    long double y = b * 1.0000 ;
    long double x2 = a2 * 1.0000 ;
    long double y2 = b2 * 1.0000 ;
    return ((y2-y) / (x2-x)) ;
}*/

bool check(int a,int b,int c)
{
    return 1ll * (v[a]*1ll - v[b] * 1ll) * (a*1ll - c*1ll) > 1ll * (v[a] * 1ll - v[c] * 1ll) * (a * 1ll - b * 1ll);
}

int solve(int l , int r)
{
    if(l >= r)
        return (l == r) ;
    int &ret = dp[l][r] ;
    if(ret != -1)
        return ret ;
    int MAX = 0 , idx = l ;
    for(int i = l ; i <= r ; ++i)
    {
        if(v[i] > MAX)
            MAX = v[i] , idx = i ;
    }
    int choice1 = solve(l , idx-1) + solve(idx+1 , r) ;
    int choice2 = 0;
    int last = idx+1 ;
    for(int i = last ; i <= r ; ++i)
    {
        i = last ;
        for(int j = i+1 ; j <= r ; ++j)
        {
            last = j ;
            if(!check(idx , i , j))
            {
                choice2 += solve(i+1 , j-1) ;
                break;
            }
        }
        if(last == r && check(idx , i , r))
            choice2 += solve(i+1 , r) ;
    }
    last = idx - 1 ;
    for(int i = last ; i >= l ; --i)
    {
        i = last ;
        for(int j = i-1 ; j >= l ; --j)
        {
            last = j ;
            if(!check(j , i , idx))
            {
                choice2 += solve(j+1 , i-1) ;
                break;
            }
        }
        if(last == l && check(l , i , idx))
            choice2 += solve(l , i-1) ;
    }
    choice2++ ;
    ret = max(choice1 , choice2) ;
    return ret ;
}
int maximum_deevs(vector<int>x)
{
    memset(dp , -1 , sizeof(dp)) ;
    v = x ;
    n = v.size() ;
    return solve(0 , n-1) ;
}

/*int main()
{
    int n ;
    cin>>n ;
    vector<int>x(n) ;
    for(auto &i : x)
        cin>>i ;
    cout<<maximum_deevs(x)<<"\n" ;
    return 0 ;
}*/

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30