Submission #1234750

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234750		Muhammad_Aneeq	Radio Towers (IOI22_towers)	C++17	15 / 100	4046 ms	7824 KiB

towers

#include "towers.h"

#include <vector>
#include <cmath>
using namespace std;
int const N=1e5+10,LG=17;
int mx[N][LG]={},dp[N]={};
bool w=1;
int k=0;
void init(int N, vector<int> H) 
{
    for (int i=0;i+1<N;i++)
    {
        if (H[i]<H[i+1])
            k=i+1;
        else
            break;
    }
    for (int i=k;i+1<N;i++)
    {
        if (H[i]>H[i+1])
            continue;
        w=0;
    }
    for (int i=0;i<N;i++)
        mx[i][0]=H[i];
    for (int i=1;(1<<i)<=N;i++)
        for (int j=0;j+(1<<i)-1<N;j++)
            mx[j][i]=max(mx[j][i-1],mx[j+(1<<(i-1))][i-1]);
}
int get(int l,int r)
{
    int lg=log2(r-l+1);
    return max(mx[l][lg],mx[r-(1<<lg)+1][lg]);
}
int max_towers(int L, int R, int D) 
{
    if (w)
    {
        if (k>L&&k<R&&max(mx[L][0],mx[R][0])+D<=mx[k][0])
            return 2;
        return 1;
    }
    int ans=0;
    for (int i=L;i<=R;i++)
    {
        dp[i]=1;
        for (int j=i-2;j>=L;j--)
        {
            if (get(j+1,i-1)-D>=max(mx[j][0],mx[i][0]))
                dp[i]=max(dp[i],dp[j]+1);
        }
        ans=max(ans,dp[i]);
    }
    return ans;
}

• Subtask 1: 4 / 4
• Subtask 2: 11 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23