Submission #1239021

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239021		AlperenT_	Radio Towers (IOI22_towers)	C++20	11 / 100	457 ms	37236 KiB

towers

#include "towers.h"

#include <vector>
#include <bits/stdc++.h> 
#pragma GCC optimize("O3,unroll-loops") 
#pragma GCC target("avx2") 
#define pb push_back
#define F first
#define pii pair<int,int> 
#define all(a) a.begin(),a.end()
#define S second 
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define ld double
#define ll long long 
using namespace std ;
const int maxn = 3000 + 10 , inf = 1e9+ 10 , mod = 998244353;
int mn[maxn][maxn] , n  ;
vector <int> h  ; 
void init(int N, std::vector<int> H) {
  n = N ; 
  h.pb(0);
  rep(i , 0 , n-1)h.pb(H[i]) ; 
  rep(l , 1 ,n){
    mn[l][l] = h[l]; 
    mn[l][l-1] = inf ; 
    rep(r , l+1 ,n){
      mn[l][r] = min(mn[l][r-1] ,h[r]) ;
    }
  }
  mn[n+1][n] = inf ;

}

int solve(int l , int r ,int d){
  int mx =  l ;
  rep(i, l ,r){
    if(h[mx] < h[i])mx = i  ;
  }
  if(mn[l][mx-1] + d > h[mx] && mn[mx+1][r]+ d > h[mx])return 1 ;
  int sm =0 ;
  if(mn[l][mx-1] + d <= h[mx])sm += solve(l,mx-1,d);
  if(mn[mx+1][r] + d <= h[mx])sm += solve(mx+1,r,d); 
  return sm ; 
}

int max_towers(int L, int R, int D) {
  L++;
  R++;
  return solve(L,R,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