Submission #1062203

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062203		vjudge1	Mountains (IOI17_mountains)	C++17	100 / 100	12 ms	16216 KiB

mountains

#include "mountains.h"
using namespace std;
int DDDP[2010][2010];
int maximum_deevs(vector<int> y) {
    int n=y.size();
    y.insert(y.begin(),0);
    DDDP[1][1]=1;
    for(int i=2;i<=n;i++){
        int uuu=i-1;
        int K=1;
        DDDP[i][i]=DDDP[i-1][i]=1;
        for(int j=i-1;--j;) {
            DDDP[j][i]=DDDP[j][i-1];
            long long ht=y[j]-y[i],dt=i-j;
            long long hb=y[uuu]-y[i],db=i-uuu;
            if(ht*db>=hb*dt) {
                K+=DDDP[j+1][uuu-1];
                uuu=j;
            }
            DDDP[j][i]=max(DDDP[j][i],DDDP[j][uuu-1]+K);
        }
    }
    return DDDP[1][n];
}

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