Submission #310011

#	Time	Username	Problem	Language	Result	Execution time	Memory
310011		ttnhuy313	Mountains (IOI17_mountains)	C++14	100 / 100	49 ms	14328 KiB

mountains

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> p;
 
int n;
vector<p> v;
int dp[2020][2020];
 
int ccw(int _a, int _b, int _c){
    p a = v[_a], b = v[_b], c = v[_c];
    ll res = a.x*b.y + b.x*c.y + c.x*a.y;
    res -= b.x*a.y + c.x*b.y + a.x*c.y;
    if(res > 0) return 1;
    if(res) return -1;
    return 0;
}
 
int maximum_deevs(vector<int> h){
    n = h.size(); v.resize(n+1);
    for(int i=1; i<=n; i++) v[i].x = i, v[i].y = h[i-1];
    for(int i=1; i<=n; i++){
        dp[i][i] = dp[i-1][i] = 1;
        int left = i - 1, v = 0;
        for(int j=i-2; j>0; j--){
            if(ccw(j, left, i) >= 0){
                v += dp[j+1][left-1];
                left = j;
            }
            dp[j][i] = max(dp[j][i-1], v + dp[j][left-1] + 1);
        }
    }
    return dp[1][n];
}

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