Submission #1026380

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026380		Mardonbekhazratov	Radio Towers (IOI22_towers)	C++17	15 / 100	4103 ms	2256 KiB

towers

#include "towers.h"

#include <vector>

using namespace std;

int n,k;
vector<int>h;
bool su1=true;


void init(int N, std::vector<int> H) {
    n=N;
    h=H;
    k=0;
    bool ok=true;
    for(int i=1;i<n;i++){
        if(h[i]>h[i-1] && ok) k=i;
        else{
            if(h[i]>h[i-1]) su1=false;
            ok=false;
        }
    }
}

int max_towers(int L, int R, int D) {
    if(su1){
        if(L<k && R>k && h[k]-D>=h[L] && h[k]-D>=h[R]) return 2;
        return 1;
    }
    vector<int>a,dp(R-L+1);
    dp[0]=1;
    for(int i=L;i<=R;i++){
        a.push_back(h[i]);
    }
    int ans=1;
    for(int i=1;i<a.size();i++){
        int mx=0;
        dp[i]=0;
        for(int j=i-1;j>=0;j--){
            if(a[j]-D>=a[i]) mx=max(a[j],mx);
            if(mx-D>=a[j]) dp[i]=max(dp[i],dp[j]);
        }
        dp[i]++;
        ans=max(ans,dp[i]);
    }
    return ans;
}

Compilation message (stderr)

towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:37:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int i=1;i<a.size();i++){
      |                 ~^~~~~~~~~

• 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