#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
int w,h;
vector<vector<int>> grid;
bool success(int mid){
vector<vector<int>> dp(w+1,vector<int>(h+1,0));
for (int i = w-1; i>=0; i--){
dp[i][h]=mid*(w-1-i);
}
for (int i = h-1; i>=0; i--){
dp[w][i]=mid*(h-1-i);
}
for (int y = h-1; y>=0; y--){
for (int x = w-1; x>=0; x--){
dp[x][y]=dp[x+1][y]+dp[x][y+1]-dp[x+1][y+1]-grid[x][y];
if (dp[x][y]<0){
return false;
}
}
}
return true;
}
int putaway(int lx, int ly, int n, int xpos[], int ypos[], int xtoys[], int ytoys[]) {
sort(xpos,xpos+lx);
sort(ypos,ypos+ly);
for (int i = 0; i<n; i++){
xtoys[i]=upper_bound(xpos,xpos+lx,xtoys[i])-xpos;
ytoys[i]=upper_bound(ypos,ypos+ly,ytoys[i])-ypos;
}
w=lx+1;
h=ly+1;
grid.resize(w,vector<int>(h,0));
for (int i = 0; i<n; i++){
grid[xtoys[i]][ytoys[i]]++;
}
if (grid[w-1][h-1]>0){
return -1;
}
int l = 0, r = n;
while (l<=r){
int mid = (l+r)/2;;
if (success(mid)){
r=mid-1;
} else {
l=mid+1;
}
}
return l;
}
