#include "aliens.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long double ld;
typedef long long ll;
typedef pair<ll,ll> pl;
vector<pl> pii, ar;
vector<pl> lines[100010]; int fr[100010], bk[100010];
vector<ll> Dp[100010];
ld cr(pl a, pl b) {
return (ld)(a.se-b.se)/(b.fi-a.fi);
}
void insert(int lev, ll p, ll q)
{
lines[lev][bk[lev]]={p,q};
while (bk[lev]>1 && cr(lines[lev][bk[lev]-1], lines[lev][bk[lev]-2])>cr(lines[lev][bk[lev]-1], lines[lev][bk[lev]])) {
lines[lev][bk[lev]-1]=lines[lev][bk[lev]]; bk[lev]--;
}
bk[lev]++;
}
ll f(int lev, ll x) {
while (fr[lev]+1<bk[lev]&&cr(lines[lev][fr[lev]], lines[lev][fr[lev]+1])<=(ld)x) fr[lev]++;
return x*x+lines[lev][fr[lev]].fi*x+lines[lev][fr[lev]].se;
}
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
int i, j;
for (i=0; i<=k; i++) {lines[i].resize(n); Dp[i].resize(n);}
for (i=0; i<n; i++) if (r[i]<c[i]) swap(r[i], c[i]);
for (i=0; i<n; i++) pii.push_back({(ll)r[i],(ll)c[i]});
sort(pii.begin(), pii.end());
for (i=0; i<n; i++) {
while (ar.size()&&ar.back().se>pii[i].se) ar.pop_back();
ar.push_back(pii[i]);
}
insert(0, -2*(ar[0].se-1), (ar[0].se-1)*(ar[0].se-1));
for (i=0; i<ar.size(); i++) {
for (j=min(i+1,k); j>=1; j--) {
Dp[j][i]=f(j-1, ar[i].fi);
if (i==n-1) continue;
if (ar[i].fi<ar[i+1].se) insert(j, -2*(ar[i+1].se-1), Dp[j][i]+(ar[i+1].se-1)*(ar[i+1].se-1));
else insert(j, -2*(ar[i+1].se-1), Dp[j][i]+(ar[i+1].se-1)*(ar[i+1].se-1)-(ar[i].fi-ar[i+1].se+1)*(ar[i].fi-ar[i+1].se+1));
}
}
ll ret=(1ll<<60);
for (i=1; i<=min((int)ar.size(), k); i++) ret=min(ret, Dp[i][ar.size()-1]);
return ret;
}
Compilation message
aliens.cpp: In function 'll take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:43:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0; i<ar.size(); i++) {
~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 4 |
2 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 4 |
3 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 4 |
4 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 12 |
5 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 52 |
6 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 210 |
7 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 88 |
8 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 7696 |
9 |
Correct |
7 ms |
5112 KB |
Correct answer: answer = 1 |
10 |
Correct |
6 ms |
5112 KB |
Correct answer: answer = 2374 |
11 |
Correct |
6 ms |
5112 KB |
Correct answer: answer = 9502 |
12 |
Correct |
6 ms |
5112 KB |
Correct answer: answer = 49 |
13 |
Correct |
6 ms |
5112 KB |
Correct answer: answer = 151 |
14 |
Correct |
6 ms |
5112 KB |
Correct answer: answer = 7550 |
15 |
Correct |
7 ms |
5112 KB |
Correct answer: answer = 7220 |
16 |
Correct |
6 ms |
5112 KB |
Correct answer: answer = 7550 |
17 |
Correct |
7 ms |
5112 KB |
Correct answer: answer = 10000 |
18 |
Correct |
6 ms |
5112 KB |
Correct answer: answer = 10000 |
19 |
Correct |
6 ms |
5112 KB |
Correct answer: answer = 624 |
20 |
Correct |
7 ms |
5112 KB |
Correct answer: answer = 10000 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 1 |
2 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 4 |
3 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 1 |
4 |
Incorrect |
6 ms |
4984 KB |
Wrong answer: output = 7, expected = 5 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 4 |
2 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 4 |
3 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 4 |
4 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 12 |
5 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 52 |
6 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 210 |
7 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 88 |
8 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 7696 |
9 |
Correct |
7 ms |
5112 KB |
Correct answer: answer = 1 |
10 |
Correct |
6 ms |
5112 KB |
Correct answer: answer = 2374 |
11 |
Correct |
6 ms |
5112 KB |
Correct answer: answer = 9502 |
12 |
Correct |
6 ms |
5112 KB |
Correct answer: answer = 49 |
13 |
Correct |
6 ms |
5112 KB |
Correct answer: answer = 151 |
14 |
Correct |
6 ms |
5112 KB |
Correct answer: answer = 7550 |
15 |
Correct |
7 ms |
5112 KB |
Correct answer: answer = 7220 |
16 |
Correct |
6 ms |
5112 KB |
Correct answer: answer = 7550 |
17 |
Correct |
7 ms |
5112 KB |
Correct answer: answer = 10000 |
18 |
Correct |
6 ms |
5112 KB |
Correct answer: answer = 10000 |
19 |
Correct |
6 ms |
5112 KB |
Correct answer: answer = 624 |
20 |
Correct |
7 ms |
5112 KB |
Correct answer: answer = 10000 |
21 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 1 |
22 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 4 |
23 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 1 |
24 |
Incorrect |
6 ms |
4984 KB |
Wrong answer: output = 7, expected = 5 |
25 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 4 |
2 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 4 |
3 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 4 |
4 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 12 |
5 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 52 |
6 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 210 |
7 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 88 |
8 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 7696 |
9 |
Correct |
7 ms |
5112 KB |
Correct answer: answer = 1 |
10 |
Correct |
6 ms |
5112 KB |
Correct answer: answer = 2374 |
11 |
Correct |
6 ms |
5112 KB |
Correct answer: answer = 9502 |
12 |
Correct |
6 ms |
5112 KB |
Correct answer: answer = 49 |
13 |
Correct |
6 ms |
5112 KB |
Correct answer: answer = 151 |
14 |
Correct |
6 ms |
5112 KB |
Correct answer: answer = 7550 |
15 |
Correct |
7 ms |
5112 KB |
Correct answer: answer = 7220 |
16 |
Correct |
6 ms |
5112 KB |
Correct answer: answer = 7550 |
17 |
Correct |
7 ms |
5112 KB |
Correct answer: answer = 10000 |
18 |
Correct |
6 ms |
5112 KB |
Correct answer: answer = 10000 |
19 |
Correct |
6 ms |
5112 KB |
Correct answer: answer = 624 |
20 |
Correct |
7 ms |
5112 KB |
Correct answer: answer = 10000 |
21 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 1 |
22 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 4 |
23 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 1 |
24 |
Incorrect |
6 ms |
4984 KB |
Wrong answer: output = 7, expected = 5 |
25 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 4 |
2 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 4 |
3 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 4 |
4 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 12 |
5 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 52 |
6 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 210 |
7 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 88 |
8 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 7696 |
9 |
Correct |
7 ms |
5112 KB |
Correct answer: answer = 1 |
10 |
Correct |
6 ms |
5112 KB |
Correct answer: answer = 2374 |
11 |
Correct |
6 ms |
5112 KB |
Correct answer: answer = 9502 |
12 |
Correct |
6 ms |
5112 KB |
Correct answer: answer = 49 |
13 |
Correct |
6 ms |
5112 KB |
Correct answer: answer = 151 |
14 |
Correct |
6 ms |
5112 KB |
Correct answer: answer = 7550 |
15 |
Correct |
7 ms |
5112 KB |
Correct answer: answer = 7220 |
16 |
Correct |
6 ms |
5112 KB |
Correct answer: answer = 7550 |
17 |
Correct |
7 ms |
5112 KB |
Correct answer: answer = 10000 |
18 |
Correct |
6 ms |
5112 KB |
Correct answer: answer = 10000 |
19 |
Correct |
6 ms |
5112 KB |
Correct answer: answer = 624 |
20 |
Correct |
7 ms |
5112 KB |
Correct answer: answer = 10000 |
21 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 1 |
22 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 4 |
23 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 1 |
24 |
Incorrect |
6 ms |
4984 KB |
Wrong answer: output = 7, expected = 5 |
25 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 4 |
2 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 4 |
3 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 4 |
4 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 12 |
5 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 52 |
6 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 210 |
7 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 88 |
8 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 7696 |
9 |
Correct |
7 ms |
5112 KB |
Correct answer: answer = 1 |
10 |
Correct |
6 ms |
5112 KB |
Correct answer: answer = 2374 |
11 |
Correct |
6 ms |
5112 KB |
Correct answer: answer = 9502 |
12 |
Correct |
6 ms |
5112 KB |
Correct answer: answer = 49 |
13 |
Correct |
6 ms |
5112 KB |
Correct answer: answer = 151 |
14 |
Correct |
6 ms |
5112 KB |
Correct answer: answer = 7550 |
15 |
Correct |
7 ms |
5112 KB |
Correct answer: answer = 7220 |
16 |
Correct |
6 ms |
5112 KB |
Correct answer: answer = 7550 |
17 |
Correct |
7 ms |
5112 KB |
Correct answer: answer = 10000 |
18 |
Correct |
6 ms |
5112 KB |
Correct answer: answer = 10000 |
19 |
Correct |
6 ms |
5112 KB |
Correct answer: answer = 624 |
20 |
Correct |
7 ms |
5112 KB |
Correct answer: answer = 10000 |
21 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 1 |
22 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 4 |
23 |
Correct |
6 ms |
4984 KB |
Correct answer: answer = 1 |
24 |
Incorrect |
6 ms |
4984 KB |
Wrong answer: output = 7, expected = 5 |
25 |
Halted |
0 ms |
0 KB |
- |