#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;
int k;
vector<pl> pii, ar;
pl lines[100010]; int Sv[100010];
int fr, bk;
ll Dp[100010], ans; int Cn[100010];
ld cr(pl a, pl b) { return (ld)(a.se-b.se)/(b.fi-a.fi); }
void insert(ll p, ll q) {
lines[bk]={p,q};
while (bk>1 && cr(lines[bk-1], lines[bk-2])>cr(lines[bk-1], lines[bk])) {
lines[bk-1]=lines[bk]; bk--;
}
bk++;
}
ll g(ll x) {
while (fr+1<bk&&cr(lines[fr], lines[fr+1])<=(ld)x) fr++;
return x*x+lines[fr].fi*x+lines[fr].se;
}
bool f(ll md)
{
fr=bk=0;
Sv[0]=Cn[0]=0;
insert(-2*(ar[1].se-1), (ar[1].se-1)*(ar[1].se-1));
for (int i=1; i<ar.size(); i++) {
Dp[i]=g(ar[i].fi)+md;
Cn[i]=Cn[Sv[fr]]+1;
if (i==ar.size()-1) continue;
insert(-2*(ar[i+1].se-1), Dp[i]+(ar[i+1].se-1)*(ar[i+1].se-1)-(ar[i].fi<ar[i+1].se?0:(ar[i].fi-ar[i+1].se+1)*(ar[i].fi-ar[i+1].se+1)));
Sv[bk-1]=i;
}
if (Cn[ar.size()-1]<=k) {
ans=min(ans, Dp[ar.size()-1]-md*Cn[ar.size()-1]);
return true;
}
return false;
}
ll take_photos(int n, int m, int _k, vector<int> r, vector<int> c) {
k=_k;
int i, j;
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());
ar.push_back({0,0});
for (i=0; i<n; i++) {
while (ar.size()>1&&ar.back().se>=pii[i].se) ar.pop_back();
ar.push_back(pii[i]);
}
ll st=-1, re=(ll)m*m;
ans=(ll)m*m;
while (st+1<re) {
ll md=(st+re)/2;
(f(md)?re:st)=md;
}
f(re);
return ans;
}
Compilation message
aliens.cpp: In function 'bool f(ll)':
aliens.cpp:35:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=1; i<ar.size(); i++) {
~^~~~~~~~~~
aliens.cpp:38:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (i==ar.size()-1) continue;
~^~~~~~~~~~~~~
aliens.cpp: In function 'll take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:51:9: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 4 |
2 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 4 |
3 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 4 |
4 |
Correct |
2 ms |
252 KB |
Correct answer: answer = 12 |
5 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 52 |
6 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 210 |
7 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 88 |
8 |
Correct |
2 ms |
348 KB |
Correct answer: answer = 7696 |
9 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 1 |
10 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 2374 |
11 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 9502 |
12 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 49 |
13 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 151 |
14 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 7550 |
15 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 7220 |
16 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 7550 |
17 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 10000 |
18 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 10000 |
19 |
Correct |
2 ms |
380 KB |
Correct answer: answer = 624 |
20 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 10000 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
380 KB |
Correct answer: answer = 1 |
2 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 4 |
3 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 1 |
4 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 5 |
5 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 41 |
6 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 71923 |
7 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 77137 |
8 |
Incorrect |
2 ms |
376 KB |
Wrong answer: output = 925, expected = 764 |
9 |
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 |
376 KB |
Correct answer: answer = 4 |
3 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 4 |
4 |
Correct |
2 ms |
252 KB |
Correct answer: answer = 12 |
5 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 52 |
6 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 210 |
7 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 88 |
8 |
Correct |
2 ms |
348 KB |
Correct answer: answer = 7696 |
9 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 1 |
10 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 2374 |
11 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 9502 |
12 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 49 |
13 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 151 |
14 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 7550 |
15 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 7220 |
16 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 7550 |
17 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 10000 |
18 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 10000 |
19 |
Correct |
2 ms |
380 KB |
Correct answer: answer = 624 |
20 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 10000 |
21 |
Correct |
2 ms |
380 KB |
Correct answer: answer = 1 |
22 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 4 |
23 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 1 |
24 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 5 |
25 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 41 |
26 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 71923 |
27 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 77137 |
28 |
Incorrect |
2 ms |
376 KB |
Wrong answer: output = 925, expected = 764 |
29 |
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 |
376 KB |
Correct answer: answer = 4 |
3 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 4 |
4 |
Correct |
2 ms |
252 KB |
Correct answer: answer = 12 |
5 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 52 |
6 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 210 |
7 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 88 |
8 |
Correct |
2 ms |
348 KB |
Correct answer: answer = 7696 |
9 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 1 |
10 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 2374 |
11 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 9502 |
12 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 49 |
13 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 151 |
14 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 7550 |
15 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 7220 |
16 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 7550 |
17 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 10000 |
18 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 10000 |
19 |
Correct |
2 ms |
380 KB |
Correct answer: answer = 624 |
20 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 10000 |
21 |
Correct |
2 ms |
380 KB |
Correct answer: answer = 1 |
22 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 4 |
23 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 1 |
24 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 5 |
25 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 41 |
26 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 71923 |
27 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 77137 |
28 |
Incorrect |
2 ms |
376 KB |
Wrong answer: output = 925, expected = 764 |
29 |
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 |
376 KB |
Correct answer: answer = 4 |
3 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 4 |
4 |
Correct |
2 ms |
252 KB |
Correct answer: answer = 12 |
5 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 52 |
6 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 210 |
7 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 88 |
8 |
Correct |
2 ms |
348 KB |
Correct answer: answer = 7696 |
9 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 1 |
10 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 2374 |
11 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 9502 |
12 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 49 |
13 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 151 |
14 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 7550 |
15 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 7220 |
16 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 7550 |
17 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 10000 |
18 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 10000 |
19 |
Correct |
2 ms |
380 KB |
Correct answer: answer = 624 |
20 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 10000 |
21 |
Correct |
2 ms |
380 KB |
Correct answer: answer = 1 |
22 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 4 |
23 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 1 |
24 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 5 |
25 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 41 |
26 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 71923 |
27 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 77137 |
28 |
Incorrect |
2 ms |
376 KB |
Wrong answer: output = 925, expected = 764 |
29 |
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 |
376 KB |
Correct answer: answer = 4 |
3 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 4 |
4 |
Correct |
2 ms |
252 KB |
Correct answer: answer = 12 |
5 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 52 |
6 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 210 |
7 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 88 |
8 |
Correct |
2 ms |
348 KB |
Correct answer: answer = 7696 |
9 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 1 |
10 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 2374 |
11 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 9502 |
12 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 49 |
13 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 151 |
14 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 7550 |
15 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 7220 |
16 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 7550 |
17 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 10000 |
18 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 10000 |
19 |
Correct |
2 ms |
380 KB |
Correct answer: answer = 624 |
20 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 10000 |
21 |
Correct |
2 ms |
380 KB |
Correct answer: answer = 1 |
22 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 4 |
23 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 1 |
24 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 5 |
25 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 41 |
26 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 71923 |
27 |
Correct |
2 ms |
376 KB |
Correct answer: answer = 77137 |
28 |
Incorrect |
2 ms |
376 KB |
Wrong answer: output = 925, expected = 764 |
29 |
Halted |
0 ms |
0 KB |
- |