Submission #120562

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
120562	2019-06-25 00:21:35	sofhiasouza	Mountains (IOI17_mountains)	C++14	100 / 100	38 ms	14332 KiB

mountains

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//In the name of God
//...
#include <iostream>
#include "mountains.h"
using namespace std;
const int N = 2016;
int n, x[N], y[N], dp[N][N];
long long rot(int a, int b, int c) { return 1ll * (x[b] - x[a]) * (y[c] - y[a]) - 1ll * (y[b] - y[a]) * (x[c] - x[a]); }
int maximum_deevs(vector<int> h) {
  int n = h.size();
  for (int i = 0; i < n; i++) {
    x[i] = i;
    y[i] = h[i];
  }
  for (int e = 1; e <= n; e++) {
    dp[e][e] = dp[e - 1][e] = 1;
    int ls = e - 1, res = 0;
    for (int b = e - 2; b > 0; b--) {
      if (rot(b - 1, ls - 1, e - 1) >= 0) { // b is seen
        res += dp[b + 1][ls - 1];
        ls = b;
      }
      dp[b][e] = max(dp[b][e - 1], 1 + res + dp[b][ls - 1]);
    }
  }
  return dp[1][n];
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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