Submission #364993

#	Time	Username	Problem	Language	Result	Execution time	Memory
364993		denkendoemeer	Mountains (IOI17_mountains)	C++14	100 / 100	41 ms	14220 KiB

mountains

#include<bits/stdc++.h>
#include "mountains.h"
using namespace std;
vector<int>x,y;
int viz(int a,int b,int c)
{
    if (1LL*(y[a]-y[b])*(x[c]-x[b])>=1LL*(x[b]-x[a])*(y[b]-y[c]))
        return 1;
    return 0;
}
int dp[2005][2005];
int maximum_deevs(vector<int>h)
{
    int n=h.size(),i;
    x.resize(n);
    y.resize(n);
    for(i=0;i<n;i++){
        x[i]=i;
        y[i]=h[i];
    }
    dp[0][0]=1;
    int j;
    for(i=1;i<n;i++){
        dp[i-1][i]=dp[i][i]=1;
        int rez=0,last=i-1;
        for(j=i-2;j>=0;j--){
            if (viz(j,last,i)){
                rez=rez+dp[j+1][last-1];
                last=j;
            }
            dp[j][i]=max(dp[j][i-1],1+rez+dp[j][last-1]);
        }
    }
    return dp[0][n-1];
}

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