Submission #755583

#	Time	Username	Problem	Language	Result	Execution time	Memory
755583		ETheBest3	Mountains (IOI17_mountains)	C++17	100 / 100	37 ms	23016 KiB

mountains

#include "mountains.h"
#define lli long long
#define endl "\n"
#include <vector>
const lli MAXN=2005;
using namespace std;
lli dp[MAXN][MAXN], N, ss, last;
struct points{
    lli x, y;
};
points p[MAXN];
bool ccw(points a, points b, points c){
    return (a.x*b.y+a.y*c.x+b.x*c.y)-(c.x*b.y+c.y*a.x+b.x*a.y)>=0;
}
int maximum_deevs(std::vector<int> y) {
    N=y.size();
    for(lli i=0; i<N; i++){
        p[i]={i, y[i]};
    }
    for(lli i=0; i<N; i++)dp[i][i]=1;
    for(lli r=0; r<N; r++){
        last=r;
        ss=0;
        for(lli l=r-1; l>=0; l--){
            dp[l][r]=dp[l][r-1];
            if(ccw(p[l], p[last], p[r])){
                ss+=dp[l+1][last-1];
                last=l;
            }
            dp[l][r]=max(dp[l][r], 1+ss+dp[l][last-1]);
        }
    }
    return dp[0][N-1];
}

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