Submission #347010

#	Time	Username	Problem	Language	Result	Execution time	Memory
347010		mohamedsobhi777	Mountains (IOI17_mountains)	C++14	100 / 100	41 ms	14208 KiB

mountains

#include "mountains.h"
#include <bits/stdc++.h>
#include <vector>

using namespace std;

const int N = 2000 + 2;

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

#define pnt complex<long long>

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

long long cross(pnt x, pnt y, pnt z)
{
       return cross(y - x, z - y);
}


int maximum_deevs(std::vector<int> y)
{
       a = y;
       int n = (int)y.size();
       for (int i = 0; i < n; ++i)
       {
              dp[i][i] = 1;
              int kah = i;
              int sum = 0;
              for (int j = i - 1; j >= 0; --j)
              {
                     dp[j][i] = dp[j][i - 1];
                     if (cross(pnt(j, a[j]), pnt(kah, a[kah]), pnt(i, a[i])) >= 0 )
                     {
                            sum += dp[j + 1][kah - 1];
                            kah = j;
                     }
                     dp[j][i] = max(dp[j][i], sum + 1 + dp[j][kah - 1]);
              }
       }
       return dp[0][n - 1];
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30