oj.uz

Submission #754853

# Submission time Handle Problem Language Result Execution time Memory
754853 2023-06-08T17:48:53 Z boris_mihov Mountains (IOI17_mountains) C++17
0 / 100
 1 ms 212 KB 
#include "mountains.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 2000 + 10;

int n;
int a[MAXN];
int rec(int l, int r)
{
    if (l > r)
    {
        return 0;
    }

    if (l == r)
    {
        return 1;
    }

    std::vector <int> max; 
    max.push_back(l - 1);
    
    int val = a[l];
    for (int i = l + 1 ; i <= r ; ++i)
    {
        val = std::max(val, a[i]);
    }

    for (int i = l ; i <= r ; ++i)
    {
        if (val == a[i])
        {
            max.push_back(i);
        }
    }

    int res = 0;
    max.push_back(r + 1);
    bool add = false;
    for (int i = 0 ; i < (int)max.size() - 1 ; ++i)
    {
        if (i > 0 && max[i - 1] == max[i] && max[i] == max[i + 1])
        {
            add = true;
        }

        res += rec(max[i] + 1, max[i + 1] - 1);
    }

    res += add;
    res = std::max(res, (int)max.size() - 2);
    return res;
}

int maximum_deevs(std::vector <int> y) 
{
    n = y.size();
    for (int i = 1 ; i <= n ; ++i)
    {
        a[i] = y[i - 1];
    }

	return rec(1, n);
}

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 30.0

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

Subtask #4
0 / 30.0

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