oj.uz

Submission #4265

# Submission time Handle Problem Language Result Execution time Memory
4265 2013-09-08T04:05:48 Z dbfud 줄 세우기 (KOI13_jul) C++
0 / 22
 1000 ms 5576 KB 
#include <iostream>

using namespace std; 

int _lis( int arr[], int n, int *max_ref)
{
    /* Base case */
    if(n == 1)
        return 1;
 
    int res, max_ending_here = 1; // length of LIS ending with arr[n-1]
 
    /* Recursively get all LIS ending with arr[0], arr[1] ... ar[n-2]. If 
       arr[i-1] is smaller than arr[n-1], and max ending with arr[n-1] needs
       to be updated, then update it */
    for(int i = 1; i < n; i++)
    {
        res = _lis(arr, i, max_ref);
        if (arr[i-1] < arr[n-1] && res + 1 > max_ending_here)
            max_ending_here = res + 1;
    }
 
    // Compare max_ending_here with the overall max. And update the
    // overall max if needed
    if (*max_ref < max_ending_here)
       *max_ref = max_ending_here;
 
    // Return length of LIS ending with arr[n-1]
    return max_ending_here;
}
 
// The wrapper function for _lis()
int lis(int arr[], int n)
{
    // The max variable holds the result
    int max = 1;
 
    // The function _lis() stores its result in max
    _lis( arr, n, &max );
 
    // returns max
    return max;
}

int main()
{
    int numChild = 0 ;
    cin >> numChild ;
    
    int *child = new int[numChild] ; 
     
    for( int i = 0 ; i < numChild ; ++i )
    {
         cin >> child[i] ; 
    }
    
    int MaxLis = lis( child, numChild ) ;
    cout << numChild - MaxLis ; 
    
 
    return 0;
}

Subtask #1
0.0 / 2.2

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1672 KB Output is correct
2 Execution timed out 1000 ms 1668 KB Program timed out
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 3.3

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 1668 KB Program timed out
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 3.3

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 1668 KB Program timed out
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 4.4

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 1668 KB Program timed out
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 4.4

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 3624 KB Program timed out
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 4.4

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 5576 KB Program timed out
2 Halted 0 ms 0 KB -