Submission #708695

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
708695	2023-03-12 07:59:40	Green55	Mountains (IOI17_mountains)	C++17	100 / 100	59 ms	32076 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
#include "mountains.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define xx first
#define yy second
#define all(v) (v).begin(), (v).end()
 
// * dp[l][r] : r을 반드시 포함하여 l~r에서 지을 수 있는 최대 개수
// k[] = r에서 보이는 점들의 인덱스들을 순서대로 쓴 배열.
// -> dp[l][r]은 k를 기준으로 partition을 나눠서, 각 최적을 합한 것과 같다.
// k[i] = k[]에서 l의 lower bound.
// opt(l ~ r) = 구간 [l~r]에서 최적 = max{l <= i <= r}(dp[l][i])
// dp[l][r] = opt(l ~ k[i]-1) + opt(k[i]+1, k[i+1]-1) + ...+ opt(k[-2]+1, k[-1]-1) + 1
 
int n, dp[2020][2020], opt[2020][2020];
ll h[2020];
 
int get_opt(int l, int r) {
  auto &ret = opt[l][r];
  if(ret != -1) return ret;
    assert(dp[l][r] != -1); assert(dp[l][r] <= r-l+1);
  ret = dp[l][r];
    if(l <= r-1) ret = max(ret, get_opt(l, r-1));
  return ret;
}
 
bool canSee(int l, int mid, int r) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

mountains.cpp: In function 'int maximum_deevs(std::vector<int>)':
mountains.cpp:53:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for(int ki=1; ki<ks.size(); ++ki) {
      |                 ~~^~~~~~~~~~

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