Submission #835113

#	Time	Username	Problem	Language	Result	Execution time	Memory
835113		gagik_2007	Radio Towers (IOI22_towers)	C++17	11 / 100	4086 ms	2888 KiB

towers

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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define ff first
#define ss second

ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=5007;
ll n,m,k;
vector<int>a;

int recurs(int l, int r, int vl, int d){
    if(l>r)return 0;
    int mx=l,mn=l;
    for(int i=l;i<=r;i++){
        if(a[i]>a[mx])mx=i;
        if(a[i]<a[mn])mn=i;
    }
    if(a[mn]>vl-d)return 0;
    int lft=recurs(l,mx-1,a[mx],d);
    int rgh=recurs(mx+1,r,a[mx],d);
    // cout<<l<<" "<<r<<" "<<vl<<" "<<d<<": ";
    if(lft==0&&rgh==0){
        // cout<<1<<endl;
        return 1;
    }
    // cout<<lft+rgh<<endl;
    return lft+rgh;
}

void init(int NN, vector<int> H) {
    n=NN;
    a=H;
}

int max_towers(int L, int R, int D) {
    return recurs(L,R,2e9+7,D);
}

• Subtask 1: 0 / 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