Submission #320858

#	Time	Username	Problem	Language	Result	Execution time	Memory
320858		knon0501	Mountains (IOI17_mountains)	C++14	40 / 100	1094 ms	512 KiB

mountains

#include "mountains.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;

long long a[2005];
int dp[2005][2005];
int visit[2005][2005];
int n;

int f(int l,int r){
    if(l>r)return 0;
    if(l==r)return 1;
    if(r==l+1)return 1;
    if(visit[l][r])return dp[l][r];
    visit[l][r]=0;
    int i,j;

    for(i=l ; i<=r ; i++){
        int k=i-1;
        int x=1;
        for(int j=i-2 ; j>=l ; j--){
            if((a[i]-a[k])*(i-j)>=(a[i]-a[j])*(i-k)){
                x+=f(j+1,k-1);
                k=j;
            }
        }
        x+=f(l,k-1);
        dp[l][r]=max(dp[l][r],x);
    }
    return dp[l][r];
}

int maximum_deevs(std::vector<int> y) {
    n=y.size();
    for(int i=1 ; i<=n ; i++)
    {
        a[i]=y[i-1];
    }
	return f(1,n);
}

Compilation message (stderr)

mountains.cpp: In function 'int f(int, int)':
mountains.cpp:17:11: warning: unused variable 'j' [-Wunused-variable]
   17 |     int i,j;
      |           ^

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