Hello,
I have been trying solving this problem: 1747 — Swap Space
Here is my WA code: https://ideone.com/64kU5M
I think the issue is with my comparator since I've seen solutions with other comparators that get AC like this one: https://github.com/morris821028/UVa/blob/master/volume017/1747%20-%20Swap%20Space.cpp
The idea behind my comparator is: if there are 2 disks to be reformatted $$$X$$$ and $$$Y$$$ and I have available storage $$$S$$$. Then if I take $$$X$$$ before $$$Y$$$
$$$S$$$ must be >= $$$X.A$$$ and $$$S + X.B - X.A$$$ >= $$$Y.A$$$, with rearragement:
$$$S >= max(X.A, Y.A - X.B + X.A)$$$
Similarly if i take $$$Y$$$ before $$$X$$$
$$$S >= max(Y.A, X.A - Y.B + Y.A)$$$
thus my comparator between $$$X$$$ and $$$Y$$$ is like this
bool cmp(pair<long long, long long> x, pair<long long, long long> y)
{
return max(x.first, x.first + y.first - x.second) < max(y.first, x.first + y.first - y.second);
}
Could somebody tell me what's wrong with my comparator?
Thanks.