Submission #1263743

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263743		abdelhakim	Obstacles for a Llama (IOI25_obstacles)	C++20	0 / 100	2093 ms	8116 KiB

obstacles

#include "obstacles.h"
#include <bits/stdc++.h>
#define ll long long
#define inf 1e17
using namespace std;

vector<ll> t;
vector<ll> h;
ll n,m;
bool free(ll x, ll y)
{
  return t[y] > h[x];
}
bool wach(ll x, ll row)
{
  ll l=x-1;
  ll r=x+1;
  ll minh=h[x];
  for (int i=0;i<row;i++)
  {
    while(r<m && free(r,i)){minh=min(minh,h[r]); r++;}
    while(l>=0 && free(l,i)){minh=min(minh,h[l]); l--;};
    if(t[i+1] <= minh)
    {
      return false;
    }
  }
  return true;
}
void initialize(std::vector<int> T, std::vector<int> H) {
  n=T.size();
  m=H.size();
  for (int i=0;i<n;i++)
  {
    t.push_back(T[i]);
  }
  for (int j=0;j<m;j++)
  {
    h.push_back(H[j]);
  }
  return;
}

bool can_reach(int L, int R, int S, int D) {
  ll maxh=0;
  for (int i=S;i<=D;i++)
  {
    maxh=max(maxh,h[i]);
  }
  ll ind=-1;
  for (int i=0;i<n;i++)
  {
    if(t[i] > maxh)
    {
      ind=i;
      break;
    }
  }
  return ind!=-1 && wach(S,ind) && wach(D,ind);
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 21
• Subtask 5: 0 / 25
• Subtask 6: 0 / 17