# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
982000 | vjudge1 | Aliens (IOI16_aliens) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct Line {
int a, b;
int idx;
double x(const auto& rhs) { return 1.0 * (rhs.b - b) / (a - rhs.a); };
int cal(const auto& x) { return a * x + b; }
};
struct CHT {
Line s[100'000 + 10];
int st = 1, ed = 0;
void add(Line nline) {
while (ed - st + 1 >= 2 && s[ed - 1].x(s[ed]) > s[ed - 1].x(nline)) ed -= 1;
s[++ed] = nline;
}
Line get(int x) {
while (ed - st + 1 >= 2 && s[st].cal(x) > s[st + 1].cal(x)) st += 1;
return s[st];
}
};
int take_photos(int n, int m, int k, vector<int> row, vector<int> column) {
using pii = pair<int, int>;
vector<pii> p(n);