oj.uz

Submission #101971

# Submission time Handle Problem Language Result Execution time Memory
101971 2019-03-21T08:28:43 Z MohamedAhmed0 Mountains (IOI17_mountains) C++14
20 / 100
 17 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] - 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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16128 KB Output is correct
2 Correct 17 ms 16000 KB Output is correct
3 Correct 15 ms 16128 KB Output is correct
4 Correct 14 ms 16128 KB Output is correct
5 Correct 16 ms 16000 KB Output is correct
6 Correct 15 ms 16000 KB Output is correct
7 Correct 15 ms 16128 KB Output is correct
8 Correct 15 ms 16128 KB Output is correct
9 Correct 13 ms 16000 KB Output is correct
10 Correct 15 ms 16000 KB Output is correct
11 Correct 14 ms 16000 KB Output is correct
12 Correct 14 ms 15988 KB Output is correct
13 Correct 15 ms 16000 KB Output is correct
14 Correct 14 ms 16000 KB Output is correct
15 Correct 15 ms 16000 KB Output is correct
16 Correct 15 ms 16128 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16128 KB Output is correct
2 Correct 17 ms 16000 KB Output is correct
3 Correct 15 ms 16128 KB Output is correct
4 Correct 14 ms 16128 KB Output is correct
5 Correct 16 ms 16000 KB Output is correct
6 Correct 15 ms 16000 KB Output is correct
7 Correct 15 ms 16128 KB Output is correct
8 Correct 15 ms 16128 KB Output is correct
9 Correct 13 ms 16000 KB Output is correct
10 Correct 15 ms 16000 KB Output is correct
11 Correct 14 ms 16000 KB Output is correct
12 Correct 14 ms 15988 KB Output is correct
13 Correct 15 ms 16000 KB Output is correct
14 Correct 14 ms 16000 KB Output is correct
15 Correct 15 ms 16000 KB Output is correct
16 Correct 15 ms 16128 KB Output is correct
17 Incorrect 13 ms 16000 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16128 KB Output is correct
2 Correct 17 ms 16000 KB Output is correct
3 Correct 15 ms 16128 KB Output is correct
4 Correct 14 ms 16128 KB Output is correct
5 Correct 16 ms 16000 KB Output is correct
6 Correct 15 ms 16000 KB Output is correct
7 Correct 15 ms 16128 KB Output is correct
8 Correct 15 ms 16128 KB Output is correct
9 Correct 13 ms 16000 KB Output is correct
10 Correct 15 ms 16000 KB Output is correct
11 Correct 14 ms 16000 KB Output is correct
12 Correct 14 ms 15988 KB Output is correct
13 Correct 15 ms 16000 KB Output is correct
14 Correct 14 ms 16000 KB Output is correct
15 Correct 15 ms 16000 KB Output is correct
16 Correct 15 ms 16128 KB Output is correct
17 Incorrect 13 ms 16000 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16128 KB Output is correct
2 Correct 17 ms 16000 KB Output is correct
3 Correct 15 ms 16128 KB Output is correct
4 Correct 14 ms 16128 KB Output is correct
5 Correct 16 ms 16000 KB Output is correct
6 Correct 15 ms 16000 KB Output is correct
7 Correct 15 ms 16128 KB Output is correct
8 Correct 15 ms 16128 KB Output is correct
9 Correct 13 ms 16000 KB Output is correct
10 Correct 15 ms 16000 KB Output is correct
11 Correct 14 ms 16000 KB Output is correct
12 Correct 14 ms 15988 KB Output is correct
13 Correct 15 ms 16000 KB Output is correct
14 Correct 14 ms 16000 KB Output is correct
15 Correct 15 ms 16000 KB Output is correct
16 Correct 15 ms 16128 KB Output is correct
17 Incorrect 13 ms 16000 KB Output isn't correct
18 Halted 0 ms 0 KB -