oj.uz

Submission #114797

# Submission time Handle Problem Language Result Execution time Memory
114797 2019-06-02T22:23:36 Z MohamedAhmed04 Mountains (IOI17_mountains) C++14
0 / 100
 14 ms 16128 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]*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 ;
    for(int i = last ; i <= r ; ++i)
    {
        i = last + 1;
        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 ;
    for(int i = last ; i >= l ; --i)
    {
        i = last - 1 ;
        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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16128 KB Output is correct
2 Correct 14 ms 16128 KB Output is correct
3 Correct 13 ms 16000 KB Output is correct
4 Correct 13 ms 16120 KB Output is correct
5 Correct 14 ms 16128 KB Output is correct
6 Incorrect 14 ms 16000 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16128 KB Output is correct
2 Correct 14 ms 16128 KB Output is correct
3 Correct 13 ms 16000 KB Output is correct
4 Correct 13 ms 16120 KB Output is correct
5 Correct 14 ms 16128 KB Output is correct
6 Incorrect 14 ms 16000 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16128 KB Output is correct
2 Correct 14 ms 16128 KB Output is correct
3 Correct 13 ms 16000 KB Output is correct
4 Correct 13 ms 16120 KB Output is correct
5 Correct 14 ms 16128 KB Output is correct
6 Incorrect 14 ms 16000 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16128 KB Output is correct
2 Correct 14 ms 16128 KB Output is correct
3 Correct 13 ms 16000 KB Output is correct
4 Correct 13 ms 16120 KB Output is correct
5 Correct 14 ms 16128 KB Output is correct
6 Incorrect 14 ms 16000 KB Output isn't correct
7 Halted 0 ms 0 KB -