Submission #101971

#	Time	Username	Problem	Language	Result	Execution time	Memory
101971		MohamedAhmed0	Mountains (IOI17_mountains)	C++14	20 / 100	17 ms	16128 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] - v[b]) * (a - c) > 1ll * (v[a] - v[c]) * (a - b);
}

int solve(int idx , int last)
{
    if(idx == n)
        return 0 ;
    int &ret = dp[idx][last] ;
    if(ret != -1)
        return ret ;
    if(last == MAX-1)
    {
        ret = max(solve(idx+1 , idx)+1 , solve(idx+1 , last));
        return ret ;
    }
    ret = solve(idx+1 , last) ;
    bool t = false ;
    long double now = v[idx] * 1.0000 ;
    long double slp = slope(idx , v[idx] , last , v[last]) ;
    for(int i = idx-1 ; i > last ; --i)
    {
        now += slp ;
        if(check(i , idx , last))
        {
            t = true ;
            break;
        }
    }
    if(t)
    {
        ret = max(ret , solve(idx+1 , idx) + 1) ;
    }
    return ret ;
}

int maximum_deevs(vector<int>x)
{
    memset(dp , -1 , sizeof(dp)) ;
    v = x ;
    n = v.size() ;
    return solve(0 , MAX-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: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30