#include "aliens.h"
#include <algorithm>
using namespace std;
typedef long long llong;
typedef long double ld;
struct point {
int x, y;
bool operator<(const point &p) const {
return x < p.x || (x == p.x && y > p.y);
}
};
int n, m, k;
vector<point> _ps;
vector<point> ps;
llong sqr(int x) {
return (llong)x * x;
}
struct line {
int cnt;
llong m, b;
} st[100000];
int top, bot;
void push(line x) {
while (top > bot && (ld)(x.b - st[top].b) / (st[top].m - x.m)
<= (ld)(st[top - 1].b - st[top].b) / (st[top].m - st[top - 1].m))
--top;
st[++top] = x;
}
llong func(line l, int x) {
return l.m * x + l.b;
}
pair<int, llong> query(int x) {
while (top > bot && func(st[bot + 1], x) <= func(st[bot], x)) ++bot;
return { st[bot].cnt, func(st[bot], x) };
}
llong dp[100000];
int cnt[100000];
//dp[i] = min(dp[j] + x[j + 1] ^ 2 - 2 * x[j + 1] * y[i] + y[i] ^ 2 + cost);
int getPhoto(llong c) {
top = -1; bot = 0;
push({ 0, -2ll * ps[0].x, sqr(ps[0].x) });
for (int i = 0; i < n; ++i) {
auto ret = query(ps[i].y + 1);
dp[i] = ret.second + sqr(ps[i].y + 1) + c;
cnt[i] = ret.first + 1;
if (i < n - 1)
push({ cnt[i], -2ll * ps[i + 1].x, dp[i] + sqr(ps[i + 1].x) });
}
return cnt[n - 1];
}
long long take_photos(int _n, int _m, int _k, vector<int> _r, vector<int> _c) {
n = _n;
m = _m;
k = _k;
_ps.reserve(n);
ps.reserve(n);
for (int i = 0; i < n; ++i) {
_ps.push_back({ min(_r[i], _c[i]), max(_r[i], _c[i]) });
}
sort(_ps.begin(), _ps.end());
for (point i : _ps) {
if (ps.empty() || ps.back().x < i.x && ps.back().y < i.y)
ps.push_back(i);
}
n = ps.size();
k = min(n, k);
llong s = 0ll, e = (llong)m * m;
int l = 0, r = n + 1;
llong lvalue, rvalue;
while (s <= e) {
llong m = (s + e) / 2;
int ret = getPhoto(m);
if (ret == k) return dp[n - 1] - ret * m;
if (ret < k) {
e = m - 1;
if (l < ret) {
l = ret; lvalue = dp[n - 1] - ret * m;
}
}
else {
s = m + 1;
if (ret < r) {
r = ret; rvalue = dp[n - 1] - ret * m;
}
}
}
return rvalue + ((lvalue - rvalue) / (r - l)) * (r - k);
}
Compilation message
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:72:39: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if (ps.empty() || ps.back().x < i.x && ps.back().y < i.y)
^
aliens.cpp:97:30: warning: 'rvalue' may be used uninitialized in this function [-Wmaybe-uninitialized]
return rvalue + ((lvalue - rvalue) / (r - l)) * (r - k);
^
aliens.cpp:97:30: warning: 'lvalue' may be used uninitialized in this function [-Wmaybe-uninitialized]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
5448 KB |
Correct answer: answer = 4 |
| 2 |
Correct |
0 ms |
5448 KB |
Correct answer: answer = 4 |
| 3 |
Correct |
0 ms |
5448 KB |
Correct answer: answer = 4 |
| 4 |
Incorrect |
0 ms |
5448 KB |
Wrong answer: output = 13, expected = 12 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
5448 KB |
Correct answer: answer = 1 |
| 2 |
Correct |
0 ms |
5448 KB |
Correct answer: answer = 4 |
| 3 |
Correct |
0 ms |
5448 KB |
Correct answer: answer = 1 |
| 4 |
Correct |
0 ms |
5448 KB |
Correct answer: answer = 5 |
| 5 |
Correct |
0 ms |
5448 KB |
Correct answer: answer = 41 |
| 6 |
Correct |
0 ms |
5448 KB |
Correct answer: answer = 71923 |
| 7 |
Correct |
0 ms |
5448 KB |
Correct answer: answer = 77137 |
| 8 |
Correct |
0 ms |
5448 KB |
Correct answer: answer = 764 |
| 9 |
Correct |
0 ms |
5448 KB |
Correct answer: answer = 250000 |
| 10 |
Correct |
0 ms |
5448 KB |
Correct answer: answer = 500 |
| 11 |
Correct |
0 ms |
5448 KB |
Correct answer: answer = 32 |
| 12 |
Correct |
0 ms |
5448 KB |
Correct answer: answer = 130050 |
| 13 |
Correct |
0 ms |
5448 KB |
Correct answer: answer = 5110 |
| 14 |
Correct |
0 ms |
5448 KB |
Correct answer: answer = 2626 |
| 15 |
Correct |
0 ms |
5448 KB |
Correct answer: answer = 796 |
| 16 |
Correct |
0 ms |
5448 KB |
Correct answer: answer = 7580 |
| 17 |
Correct |
0 ms |
5448 KB |
Correct answer: answer = 1904 |
| 18 |
Correct |
0 ms |
5448 KB |
Correct answer: answer = 996004 |
| 19 |
Correct |
0 ms |
5448 KB |
Correct answer: answer = 38817 |
| 20 |
Correct |
0 ms |
5448 KB |
Correct answer: answer = 4096 |
| 21 |
Correct |
0 ms |
5448 KB |
Correct answer: answer = 1 |
| 22 |
Correct |
0 ms |
5448 KB |
Correct answer: answer = 1 |
| 23 |
Correct |
0 ms |
5448 KB |
Correct answer: answer = 2040 |
| 24 |
Correct |
0 ms |
5448 KB |
Correct answer: answer = 2 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
5448 KB |
Correct answer: answer = 4 |
| 2 |
Correct |
0 ms |
5448 KB |
Correct answer: answer = 4 |
| 3 |
Correct |
0 ms |
5448 KB |
Correct answer: answer = 4 |
| 4 |
Incorrect |
0 ms |
5448 KB |
Wrong answer: output = 13, expected = 12 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
5448 KB |
Correct answer: answer = 4 |
| 2 |
Correct |
0 ms |
5448 KB |
Correct answer: answer = 4 |
| 3 |
Correct |
0 ms |
5448 KB |
Correct answer: answer = 4 |
| 4 |
Incorrect |
0 ms |
5448 KB |
Wrong answer: output = 13, expected = 12 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
5448 KB |
Correct answer: answer = 4 |
| 2 |
Correct |
0 ms |
5448 KB |
Correct answer: answer = 4 |
| 3 |
Correct |
0 ms |
5448 KB |
Correct answer: answer = 4 |
| 4 |
Incorrect |
0 ms |
5448 KB |
Wrong answer: output = 13, expected = 12 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
5448 KB |
Correct answer: answer = 4 |
| 2 |
Correct |
0 ms |
5448 KB |
Correct answer: answer = 4 |
| 3 |
Correct |
0 ms |
5448 KB |
Correct answer: answer = 4 |
| 4 |
Incorrect |
0 ms |
5448 KB |
Wrong answer: output = 13, expected = 12 |
| 5 |
Halted |
0 ms |
0 KB |
- |
