#include "aliens.h"
#include <algorithm>
#include <vector>
#include <stdio.h>
typedef struct point point;
struct point
{
long long r, c;
};
point P[100005];
long long DP[2][100005];
int sortP(point a, point b)
{
return (a.r < b.r || (a.r == b.r && a.c < b.c));
}
long long min(long long a, long long b)
{
return (a < b)?a:b;
}
long long max(long long a, long long b)
{
return (a > b)?a:b;
}
typedef struct line line;
struct line
{
long long m, c;
double s;
};
std::vector<line> L;
double intersect(line a, line b)
{
if (a.m == b.m)
{
if (b.c >= a.c)
return 1e18;
else
return -1e18;
}
else
return (double) (a.c - b.c)/(b.m - a.m);
}
void insertLine(line l)
{
// printf("insertLine %lld %lld %lf\n", l.m, l.c, l.s);
double r;
while (!L.empty() && (r = intersect(L.back(), l)) <= L.back().s)
L.pop_back();
if (r == 1e18)
return;
if (L.empty())
{
l.s = -1e18;
L.push_back(l);
}
else
{
l.s = r;
L.push_back(l);
}
}
int compare(line e, long long v)
{
return e.s < v;
}
long long getLine(long long x)
{
// int i;
// for (i = 0; i < L.size(); i++)
// printf("line %lld %lld %lf\n", L[i].m, L[i].c, L[i].s);
int j = std::lower_bound(L.begin(), L.end(), x, compare) - L.begin();
if (j == L.size() || L[j].s > x) j--;
// printf("getLine x%lld j%d %lld\n", x, j, L[j].m*x + L[j].c);
return L[j].m*x + L[j].c;
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
int i, j;
long long Ans;
for (i = 0; i < n; i++)
{
P[i].r = min(r[i], c[i]);
P[i].c = max(r[i], c[i]);
}
std::sort(&P[0], &P[n], sortP);
for (j = 0; j < n; j++)
{
DP[1][j] = (P[j].c - P[0].r + 1)*(P[j].c - P[0].r + 1);
// printf("%lld\n", DP[1][j]);
}
// printf("\n");
Ans = DP[1][n - 1];
line l;
double rr;
for (i = 2; i <= k; i++)
{
L.clear();
L.push_back({0, 1000000000000000000LL, -1e18});
for (j = 0; j < n; j++)
{
// if (j > 0)
// insertLine({-2LL*(P[j].r - 1), DP[(i+1)%2][j - 1] + (P[j].r - 1)*(P[j].r - 1), -1e18});
if (j > 0)
{
if (P[j - 1].c >= P[j].r)
insertLine({-2LL*(P[j].r - 1), DP[(i+1)%2][j - 1] - P[j - 1].c*P[j - 1].c + 2LL*P[j - 1].c*(P[j].r - 1), -1e18});
else
insertLine({-2LL*(P[j].r - 1), DP[(i+1)%2][j - 1] + (P[j].r - 1)*(P[j].r - 1), -1e18});
// l = {-2LL*(P[j].r - 1), DP[(i+1)%2][j - 1] + (P[j].r - 1)*(P[j].r - 1), P[j].r + 1};
// if (L.back().s >= l.s)
// L.pop_back();
// while (!L.empty() && (rr = intersect(L.back(), l)) <= L.back().s)
// L.pop_back();
// if (rr != 1e18)
// l.s = rr;
// L.push_back(l);
}
DP[i%2][j] = getLine(P[j].c) + P[j].c*P[j].c;
// printf("%lld\n", DP[i%2][j]);
}
// printf("\n");
Ans = min(Ans, DP[i%2][n - 1]);
}
return Ans;
}
Compilation message
aliens.cpp: In function 'long long int getLine(long long int)':
aliens.cpp:72:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (j == L.size() || L[j].s > x) j--;
~~^~~~~~~~~~~
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:92:10: warning: unused variable 'l' [-Wunused-variable]
line l;
^
aliens.cpp:93:12: warning: unused variable 'rr' [-Wunused-variable]
double rr;
^~
aliens.cpp: In function 'void insertLine(line)':
aliens.cpp:49:5: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
if (r == 1e18)
^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 4 |
2 |
Correct |
2 ms |
488 KB |
Correct answer: answer = 4 |
3 |
Correct |
2 ms |
488 KB |
Correct answer: answer = 4 |
4 |
Incorrect |
2 ms |
492 KB |
Wrong answer: output = 7, expected = 12 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
492 KB |
Correct answer: answer = 1 |
2 |
Correct |
2 ms |
544 KB |
Correct answer: answer = 4 |
3 |
Correct |
2 ms |
544 KB |
Correct answer: answer = 1 |
4 |
Correct |
2 ms |
544 KB |
Correct answer: answer = 5 |
5 |
Correct |
2 ms |
608 KB |
Correct answer: answer = 41 |
6 |
Correct |
2 ms |
608 KB |
Correct answer: answer = 71923 |
7 |
Correct |
2 ms |
616 KB |
Correct answer: answer = 77137 |
8 |
Correct |
6 ms |
648 KB |
Correct answer: answer = 764 |
9 |
Correct |
2 ms |
652 KB |
Correct answer: answer = 250000 |
10 |
Correct |
9 ms |
656 KB |
Correct answer: answer = 500 |
11 |
Correct |
2 ms |
660 KB |
Correct answer: answer = 32 |
12 |
Correct |
2 ms |
668 KB |
Correct answer: answer = 130050 |
13 |
Correct |
3 ms |
708 KB |
Correct answer: answer = 5110 |
14 |
Correct |
2 ms |
708 KB |
Correct answer: answer = 2626 |
15 |
Correct |
3 ms |
844 KB |
Correct answer: answer = 796 |
16 |
Correct |
3 ms |
844 KB |
Correct answer: answer = 7580 |
17 |
Correct |
4 ms |
844 KB |
Correct answer: answer = 1904 |
18 |
Correct |
2 ms |
844 KB |
Correct answer: answer = 996004 |
19 |
Correct |
2 ms |
844 KB |
Correct answer: answer = 38817 |
20 |
Correct |
4 ms |
844 KB |
Correct answer: answer = 4096 |
21 |
Correct |
2 ms |
844 KB |
Correct answer: answer = 1 |
22 |
Correct |
6 ms |
844 KB |
Correct answer: answer = 1 |
23 |
Correct |
4 ms |
844 KB |
Correct answer: answer = 2040 |
24 |
Correct |
7 ms |
844 KB |
Correct answer: answer = 2 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 4 |
2 |
Correct |
2 ms |
488 KB |
Correct answer: answer = 4 |
3 |
Correct |
2 ms |
488 KB |
Correct answer: answer = 4 |
4 |
Incorrect |
2 ms |
492 KB |
Wrong answer: output = 7, expected = 12 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 4 |
2 |
Correct |
2 ms |
488 KB |
Correct answer: answer = 4 |
3 |
Correct |
2 ms |
488 KB |
Correct answer: answer = 4 |
4 |
Incorrect |
2 ms |
492 KB |
Wrong answer: output = 7, expected = 12 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 4 |
2 |
Correct |
2 ms |
488 KB |
Correct answer: answer = 4 |
3 |
Correct |
2 ms |
488 KB |
Correct answer: answer = 4 |
4 |
Incorrect |
2 ms |
492 KB |
Wrong answer: output = 7, expected = 12 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 4 |
2 |
Correct |
2 ms |
488 KB |
Correct answer: answer = 4 |
3 |
Correct |
2 ms |
488 KB |
Correct answer: answer = 4 |
4 |
Incorrect |
2 ms |
492 KB |
Wrong answer: output = 7, expected = 12 |
5 |
Halted |
0 ms |
0 KB |
- |