Submission #1263889

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263889		abdelhakim	Obstacles for a Llama (IOI25_obstacles)	C++20	21 / 100	2092 ms	6472 KiB

obstacles

#include "obstacles.h"
#include <bits/stdc++.h>
#define ll long long
#define inf 1e17
#define dbg(x) cerr<<#x<< ' '<<x<<endl;
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 lft, ll rgt)
{
  ll l=x-1;
  ll r=x+1;
  ll minh=h[x];
  for (int i=0;i<row;i++)
  {
    while(r<rgt+1 && free(r,i)){minh=min(minh,h[r]); r++;}
    while(l>=lft && 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) {
  t.assign(T.begin(), T.end());
  h.assign(H.begin(), H.end());
  n = t.size();
  m = h.size();
  return;
}

bool can_reach(int L, int R, int S, int D) {
  if(D<S)swap(D,S);
  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;
    }
  }
  if((ind!=-1) & wach(S,ind, L, R) & wach(D,ind,L,R)) return 1;
  else return 0;
}

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