#include "robots.h"
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
int ceil_div(int a, int b)
{
return a/b + ((a%b) ? 1 : 0);
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
sort(X, X+A, [] (int x, int y)
{
return x > y;
});
sort(Y, Y+B, [] (int x, int y)
{
return x > y;
});
int ct[A+1][B+1];
for(int i = 0; i <= A; i++)
for(int j = 0; j <= B; j++)
ct[i][j] = 0;
for(int j = 0; j < T; j++)
{
int bitI = -1;
for(int b = 18; b >= 0; b--)
{
if(bitI + (1 << b) >= A) continue;
if(X[bitI + (1 << b)] <= W[j]) continue;
bitI += (1 << b);
}
int bitJ = -1;
for(int b = 18; b >= 0; b--)
{
if(bitJ + (1 << b) >= B) continue;
if(Y[bitJ + (1 << b)] <= S[j]) continue;
bitJ += (1 << b);
}
ct[bitI+1][bitJ+1]++;
}
if(ct[0][0]) return -1;
for(int i = 0; i <= A; i++)
{
for(int j = 0; j <= B; j++)
{
if(i > 0)
ct[i][j] += ct[i-1][j];
if(j > 0)
ct[i][j] += ct[i][j-1];
if(i > 0 && j > 0)
ct[i][j] -= ct[i-1][j-1];
}
}
int res = 0;
for(int i = 0; i <= A; i++)
{
for(int j = 0; j <= B; j++)
{
// cerr << ct[i][j] << ' ';
if(i+j == 0) continue;
res = max(res, ceil_div(ct[i][j], i+j));
}
// cerr << '\n';
}
// int sm = 0;
//
// if(ct[0]) return -1;
// for(int i = 1; i <= A; i++)
// {
// sm += ct[i];
// res = max(res, sm/i + ((sm%i) ? 1 : 0));
// }
return res;
}
//Subtask 2: 1D
/*
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
sort(X, X+A, [] (int x, int y)
{
return x > y;
});
vector<int> ct(A+1, 0);
for(int j = 0; j < T; j++)
{
int bit = -1; //locate last robot that can handle toy j
for(int b = 18; b >= 0; b--)
{
if(bit + (1 << b) >= A) continue;
if(X[bit + (1 << b)] <= W[j]) continue;
bit += (1 << b);
}
ct[bit+1]++;
}
int res = 0;
int sm = 0;
if(ct[0]) return -1;
for(int i = 1; i <= A; i++)
{
sm += ct[i];
res = max(res, sm/i + ((sm%i) ? 1 : 0));
}
return res;
}
*/
