oj.uz

Submission #101969

# Submission time Handle Problem Language Result Execution time Memory
101969 2019-03-21T08:22:24 Z MohamedAhmed0 Mountains (IOI17_mountains) C++14
0 / 100
 14 ms 16256 KB 
#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 , last , idx))
        {
            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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16128 KB Output is correct
2 Correct 14 ms 16256 KB Output is correct
3 Incorrect 14 ms 16128 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16128 KB Output is correct
2 Correct 14 ms 16256 KB Output is correct
3 Incorrect 14 ms 16128 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16128 KB Output is correct
2 Correct 14 ms 16256 KB Output is correct
3 Incorrect 14 ms 16128 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16128 KB Output is correct
2 Correct 14 ms 16256 KB Output is correct
3 Incorrect 14 ms 16128 KB Output isn't correct
4 Halted 0 ms 0 KB -