Submission #203569

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
203569	2020-02-21 10:52:11	anonymous	Mountains (IOI17_mountains)	C++14	100 / 100	57 ms	8568 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 <vector>
#define MAXN 2005
using namespace std;
int N, dp[MAXN][MAXN];
long long H[MAXN];
bool block(int i, int j, int k) {
    //does j block view of i to k (i<=j<=k)?
    if (j == k || j == i) {return(false);}
    return((H[k]-H[j])*(k-i) < (H[k]-H[i])*(k-j));
}
int slv(int l, int r) {
    if (l >= r) {return(max(r-l+1,0));}
    if (dp[l][r]) {return(dp[l][r]);}
    int peak=0, lh, rh, val=1;
    for (int i=l; i<=r; i++) {
        if (H[i] >= H[peak]) {
            peak=i;
        }
    }
    dp[l][r]=slv(l, peak-1) + slv(peak+1,r); //ignore cur
    lh = peak, rh = peak;
    for (int i=peak-1; i>=l; i--) {
        if (block(i, lh, peak)) {continue;}
        else {
            val += slv(i+1, lh-1);
            lh = i;
        }
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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