#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define fr first
#define sc second
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)
int pt = 0;
vector <pair<int, int>> segments;
void erase_useless(){
vector <pair<int,int>> tz;
for(auto it : segments){
if(!tz.size()){
tz.push_back(it);
}
else{
auto it1 = tz.back();
if(it1.fr >= it.fr && it1.sc <= it.sc){
tz.pop_back();
tz.push_back(it);
}
else if(it.fr >= it1.fr && it.sc <= it1.sc){
continue;
}
else{
tz.push_back(it);
}
}
}
segments = tz;
}
struct line{
int slope, cons;
long double pbegin;
};
long double intersect(line A, line B){
return (long double) (B.cons - A.cons) / (A.slope - B.slope);
}
struct CHT{
vector <line> hull;
void add(line TZ){
if(hull.empty()){
TZ.pbegin = -1.0;
hull.push_back(TZ);
}
else{
while((int)hull.size() >= 2){
if(intersect(TZ, hull.back()) <= intersect(hull.back(), hull[(int)hull.size() - 2])){
hull.pop_back();
}
else{
break;
}
}
TZ.pbegin = intersect(TZ, hull.back());
hull.push_back(TZ);
}
}
int query(double x){
if(pt == (int)hull.size() - 1){
return hull[pt].slope * x + hull[pt].cons;
}
else{
while(hull[pt + 1].pbegin <= x){
++pt;
}
return hull[pt].slope * x + hull[pt].cons;
}
}
};
CHT solution;
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c){
vector < vector <int>> dp(n + 5, vector <int> (k + 5));
for(int i=0;i<n;i++){
segments.push_back({min(r[i], c[i]), max(r[i], c[i])});
}
sort(all(segments));
erase_useless();
n = (int)segments.size();
segments.push_back({0, 0});
for(int i=1;i<=n;i++){
dp[i][1] = (segments[i - 1].sc - segments[0].fr + 1) * (segments[i - 1].sc - segments[0].fr + 1);
}
for(int j=2;j<=k;j++){
pt = 0;
solution.hull.clear();
dp[1][j] = dp[1][j - 1];
solution.add({2 - 2*segments[1].fr, dp[1][j - 1] + (segments[1].fr - 1) * (segments[1].fr - 1) - max(0, segments[0].sc - segments[1].fr + 1) * max(0, segments[0].sc - segments[1].fr + 1), 0.0});
for(int i=2;i<=n;i++){
dp[i][j] = dp[i][j - 1];
dp[i][j] = min(dp[i][j], solution.query(segments[i - 1].sc) + segments[i - 1].sc * segments[i - 1].sc);
solution.add({2 - 2*segments[i].fr, dp[i][j-1] + (segments[i].fr - 1) * (segments[i].fr - 1) - max(0, segments[i - 1].sc - segments[i].fr + 1) * max(0, segments[i - 1].sc - segments[i].fr + 1), 0.0});
}
}
return dp[n][k];
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 4 |
2 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 4 |
3 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 4 |
4 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 12 |
5 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 11 |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 1 |
2 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 4 |
3 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 1 |
4 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 11 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 4 |
2 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 4 |
3 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 4 |
4 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 12 |
5 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 11 |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 4 |
2 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 4 |
3 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 4 |
4 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 12 |
5 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 11 |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 4 |
2 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 4 |
3 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 4 |
4 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 12 |
5 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 11 |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 4 |
2 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 4 |
3 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 4 |
4 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 12 |
5 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 11 |
6 |
Halted |
0 ms |
0 KB |
- |