oj.uz

Submission #364984

# Submission time Handle Problem Language Result Execution time Memory
364984 2021-02-10T17:06:23 Z denkendoemeer Mountains (IOI17_mountains) C++14
0 / 100
 1 ms 364 KB 
#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[b]-y[c])*(x[a]-x[b])<=1LL*(x[b]-x[c])*(y[a]-y[b]))
        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=2;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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -