Submission #257360

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
257360	2020-08-04 07:08:06	Fischer	Mountains (IOI17_mountains)	C++14	100 / 100	52 ms	16256 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
#include "mountains.h"
#include <bits/stdc++.h>
int maximum_deevs(std::vector<int> y) {
  int n = y.size();
  std::vector<int> last(n, -1);
  std::vector<std::vector<int>> memo(n+1, std::vector<int>(n+1, 0));
  for (int i = 0; i < n; ++i) {
    memo[i][i] = 1;
  }
  for (int len = 2; len <= n; ++len) {
    for (int i = 0; i < n; ++i) {
      int nxt = i + len - 1;
      if (nxt >= n) continue;
      memo[i][nxt] = memo[i+1][nxt];
      if (last[i] == -1 ||
          (last[i] - i) *1ll* (y[nxt] - y[i]) >= (nxt - i) *1ll* (y[last[i]] - y[i])) {
        last[i] = nxt;
      }
      memo[i][nxt] = std::max(memo[i][nxt], memo[i][last[i]-1] + memo[last[i]+1][nxt]);
    }
  }
  return memo[0][n-1];
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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