oj.uz

Submission #346963

# Submission time Handle Problem Language Result Execution time Memory
346963 2021-01-11T12:27:06 Z mohamedsobhi777 Mountains (IOI17_mountains) C++14
0 / 100
 1 ms 364 KB 
#include "mountains.h"
#include <bits/stdc++.h>
#include <vector>

using namespace std;

const int N = 2000 + 2;

int dp[N];
vector<int> a;

#define pnt complex<long long>

long long cross(pnt x, pnt y)
{
       return imag(conj(x) * y);
}

bool isR(pnt x, pnt y, pnt z)
{
       return cross(y - x, z - y) < 0;
}

bool see(int i, int j)
{
       pnt x(i, a[i]), y(j, a[j]);
       for (int k = i + 1; k < j; ++k)
       {
              pnt z(k, a[k]);
              if (isR(x, z, y))
              {
                     return 0;
              }
       }
       return 1;
}

int maximum_deevs(std::vector<int> y)
{
       a = y;
       dp[0] = 1;
       int n = (int)y.size();
       for (int i = 1; i < n; ++i)
       {
              for (int j = i - 1; ~j; --j)
              {
                     if (!see(j, i))
                     {
                            dp[i] = max(dp[i], dp[j] + 1);
                     }
              }
       }
       return *max_element(dp, dp + N);
}

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 30.0

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

Subtask #4
0 / 30.0

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