#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 6;
const ll INF = 1e12;
ll dp[MAXN];
int opt[MAXN];
vector<pair<ll,ll> > inter;
struct Line{
int id;
ll m,c;
ll f(ll x){
return m*x+c;
}
};
vector<Line> cht;
bool check(Line f1,Line f2,Line f3){
return (f1.c-f3.c)*(f1.m-f3.m) > (f1.c-f2.c)*(f1.m-f2.m);
}
void ins(Line fn){
while(cht.size() > 1 && check(cht[cht.size()-2],cht.back(),fn)){
cht.pop_back();
}
cht.push_back(fn);
}
Line query(ll x){
int l=0,r=cht.size()-1;
while(l < r){
int m = (l+r)/2;
if(cht[m].f(x) < cht[m+1].f(x)) r = m;
else l = m+1;
}
return cht[l];
}
int run(ll cost){
memset(dp,1,sizeof(dp));
memset(opt,1,sizeof(opt));
dp[0] = opt[0] = 0;
ins({0,-2*inter[0].first,inter[0].first*inter[0].first});
for(int i=0;i<inter.size();i++){
Line q = query(inter[i].second);
ll nx = cost+inter[i].second*inter[i].second+q.f(inter[i].second);
if(nx < dp[i+1]){
dp[i+1] = nx;
opt[i+1] = q.id;
}
if(i+1 < inter.size()){
if(inter[i+1].first <= inter[i].second) ins({i+1,-2*inter[i+1].first,dp[i+1]-inter[i].second*(inter[i].second-2*inter[i+1].first)});
else ins({i+1,-2*inter[i+1].first,dp[i+1]+inter[i+1].first*inter[i+1].first});
}
}
cht.clear();
int cnt=0,idx=inter.size();
while(idx > 0){
idx = opt[idx];
cnt++;
}
return cnt;
}
ll take_photos(int n,int m,int k,vector<int> r,vector<int> c){
for(int i=0;i<n;i++) inter.emplace_back(1ll*min(r[i],c[i]),1ll*max(r[i],c[i])+1);
sort(inter.begin(),inter.end());
vector<pair<ll,ll> > temp;
for(int i=0;i<n;i++){
while(temp.size() > 0 && temp.back().first == inter[i].first && temp.back().second <= inter[i].second) temp.pop_back();
if(temp.empty() || temp.back().second < inter[i].second) temp.push_back(inter[i]);
}
swap(temp,inter);
k = min(k,(int)inter.size());
ll L=0,R=INF;
while(L < R){
ll M = (L+R+1)/2;
if(run(M) < k) R = M-1;
else L = M;
}
run(L);
return dp[inter.size()]-L*k;
}
Compilation message
aliens.cpp: In function 'int run(ll)':
aliens.cpp:43:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for(int i=0;i<inter.size();i++){
| ~^~~~~~~~~~~~~
aliens.cpp:50:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | if(i+1 < inter.size()){
| ~~~~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1444 KB |
Correct answer: answer = 4 |
2 |
Correct |
3 ms |
1432 KB |
Correct answer: answer = 4 |
3 |
Correct |
2 ms |
1360 KB |
Correct answer: answer = 4 |
4 |
Correct |
3 ms |
1356 KB |
Correct answer: answer = 12 |
5 |
Correct |
3 ms |
1448 KB |
Correct answer: answer = 52 |
6 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 210 |
7 |
Correct |
3 ms |
1448 KB |
Correct answer: answer = 88 |
8 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 7696 |
9 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 1 |
10 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 2374 |
11 |
Correct |
3 ms |
1464 KB |
Correct answer: answer = 9502 |
12 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 49 |
13 |
Correct |
2 ms |
1452 KB |
Correct answer: answer = 151 |
14 |
Correct |
3 ms |
1484 KB |
Correct answer: answer = 7550 |
15 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 7220 |
16 |
Correct |
2 ms |
1432 KB |
Correct answer: answer = 7550 |
17 |
Correct |
2 ms |
1448 KB |
Correct answer: answer = 10000 |
18 |
Correct |
2 ms |
1448 KB |
Correct answer: answer = 10000 |
19 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 624 |
20 |
Correct |
3 ms |
1448 KB |
Correct answer: answer = 10000 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1348 KB |
Correct answer: answer = 1 |
2 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 4 |
3 |
Correct |
2 ms |
1440 KB |
Correct answer: answer = 1 |
4 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 5 |
5 |
Incorrect |
3 ms |
1356 KB |
Wrong answer: output = 69, expected = 41 |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1444 KB |
Correct answer: answer = 4 |
2 |
Correct |
3 ms |
1432 KB |
Correct answer: answer = 4 |
3 |
Correct |
2 ms |
1360 KB |
Correct answer: answer = 4 |
4 |
Correct |
3 ms |
1356 KB |
Correct answer: answer = 12 |
5 |
Correct |
3 ms |
1448 KB |
Correct answer: answer = 52 |
6 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 210 |
7 |
Correct |
3 ms |
1448 KB |
Correct answer: answer = 88 |
8 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 7696 |
9 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 1 |
10 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 2374 |
11 |
Correct |
3 ms |
1464 KB |
Correct answer: answer = 9502 |
12 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 49 |
13 |
Correct |
2 ms |
1452 KB |
Correct answer: answer = 151 |
14 |
Correct |
3 ms |
1484 KB |
Correct answer: answer = 7550 |
15 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 7220 |
16 |
Correct |
2 ms |
1432 KB |
Correct answer: answer = 7550 |
17 |
Correct |
2 ms |
1448 KB |
Correct answer: answer = 10000 |
18 |
Correct |
2 ms |
1448 KB |
Correct answer: answer = 10000 |
19 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 624 |
20 |
Correct |
3 ms |
1448 KB |
Correct answer: answer = 10000 |
21 |
Correct |
2 ms |
1348 KB |
Correct answer: answer = 1 |
22 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 4 |
23 |
Correct |
2 ms |
1440 KB |
Correct answer: answer = 1 |
24 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 5 |
25 |
Incorrect |
3 ms |
1356 KB |
Wrong answer: output = 69, expected = 41 |
26 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1444 KB |
Correct answer: answer = 4 |
2 |
Correct |
3 ms |
1432 KB |
Correct answer: answer = 4 |
3 |
Correct |
2 ms |
1360 KB |
Correct answer: answer = 4 |
4 |
Correct |
3 ms |
1356 KB |
Correct answer: answer = 12 |
5 |
Correct |
3 ms |
1448 KB |
Correct answer: answer = 52 |
6 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 210 |
7 |
Correct |
3 ms |
1448 KB |
Correct answer: answer = 88 |
8 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 7696 |
9 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 1 |
10 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 2374 |
11 |
Correct |
3 ms |
1464 KB |
Correct answer: answer = 9502 |
12 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 49 |
13 |
Correct |
2 ms |
1452 KB |
Correct answer: answer = 151 |
14 |
Correct |
3 ms |
1484 KB |
Correct answer: answer = 7550 |
15 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 7220 |
16 |
Correct |
2 ms |
1432 KB |
Correct answer: answer = 7550 |
17 |
Correct |
2 ms |
1448 KB |
Correct answer: answer = 10000 |
18 |
Correct |
2 ms |
1448 KB |
Correct answer: answer = 10000 |
19 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 624 |
20 |
Correct |
3 ms |
1448 KB |
Correct answer: answer = 10000 |
21 |
Correct |
2 ms |
1348 KB |
Correct answer: answer = 1 |
22 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 4 |
23 |
Correct |
2 ms |
1440 KB |
Correct answer: answer = 1 |
24 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 5 |
25 |
Incorrect |
3 ms |
1356 KB |
Wrong answer: output = 69, expected = 41 |
26 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1444 KB |
Correct answer: answer = 4 |
2 |
Correct |
3 ms |
1432 KB |
Correct answer: answer = 4 |
3 |
Correct |
2 ms |
1360 KB |
Correct answer: answer = 4 |
4 |
Correct |
3 ms |
1356 KB |
Correct answer: answer = 12 |
5 |
Correct |
3 ms |
1448 KB |
Correct answer: answer = 52 |
6 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 210 |
7 |
Correct |
3 ms |
1448 KB |
Correct answer: answer = 88 |
8 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 7696 |
9 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 1 |
10 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 2374 |
11 |
Correct |
3 ms |
1464 KB |
Correct answer: answer = 9502 |
12 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 49 |
13 |
Correct |
2 ms |
1452 KB |
Correct answer: answer = 151 |
14 |
Correct |
3 ms |
1484 KB |
Correct answer: answer = 7550 |
15 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 7220 |
16 |
Correct |
2 ms |
1432 KB |
Correct answer: answer = 7550 |
17 |
Correct |
2 ms |
1448 KB |
Correct answer: answer = 10000 |
18 |
Correct |
2 ms |
1448 KB |
Correct answer: answer = 10000 |
19 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 624 |
20 |
Correct |
3 ms |
1448 KB |
Correct answer: answer = 10000 |
21 |
Correct |
2 ms |
1348 KB |
Correct answer: answer = 1 |
22 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 4 |
23 |
Correct |
2 ms |
1440 KB |
Correct answer: answer = 1 |
24 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 5 |
25 |
Incorrect |
3 ms |
1356 KB |
Wrong answer: output = 69, expected = 41 |
26 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1444 KB |
Correct answer: answer = 4 |
2 |
Correct |
3 ms |
1432 KB |
Correct answer: answer = 4 |
3 |
Correct |
2 ms |
1360 KB |
Correct answer: answer = 4 |
4 |
Correct |
3 ms |
1356 KB |
Correct answer: answer = 12 |
5 |
Correct |
3 ms |
1448 KB |
Correct answer: answer = 52 |
6 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 210 |
7 |
Correct |
3 ms |
1448 KB |
Correct answer: answer = 88 |
8 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 7696 |
9 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 1 |
10 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 2374 |
11 |
Correct |
3 ms |
1464 KB |
Correct answer: answer = 9502 |
12 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 49 |
13 |
Correct |
2 ms |
1452 KB |
Correct answer: answer = 151 |
14 |
Correct |
3 ms |
1484 KB |
Correct answer: answer = 7550 |
15 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 7220 |
16 |
Correct |
2 ms |
1432 KB |
Correct answer: answer = 7550 |
17 |
Correct |
2 ms |
1448 KB |
Correct answer: answer = 10000 |
18 |
Correct |
2 ms |
1448 KB |
Correct answer: answer = 10000 |
19 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 624 |
20 |
Correct |
3 ms |
1448 KB |
Correct answer: answer = 10000 |
21 |
Correct |
2 ms |
1348 KB |
Correct answer: answer = 1 |
22 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 4 |
23 |
Correct |
2 ms |
1440 KB |
Correct answer: answer = 1 |
24 |
Correct |
2 ms |
1356 KB |
Correct answer: answer = 5 |
25 |
Incorrect |
3 ms |
1356 KB |
Wrong answer: output = 69, expected = 41 |
26 |
Halted |
0 ms |
0 KB |
- |