Submission #346966

#	Time	Username	Problem	Language	Result	Execution time	Memory
346966		mohamedsobhi777	Mountains (IOI17_mountains)	C++14	20 / 100	1 ms	492 KiB

mountains

#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)
       {
              dp[i] = 1;
              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: 20 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30