이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
#include "aliens.h"
using namespace std;
struct line{
long long m ,b;
};
struct hull : vector<line>{
void add(long long m ,long long b){
push_back({m ,b});
}
long long eval(long long x){
long long ret = LLONG_MAX;
for(auto&l : *this)
ret = min(ret ,x*l.m+l.b);
return ret;
}
};
long long sqr(long long num){
return num*num;
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
vector <pair<int ,int>> rngs ,po;
for(int i=0; i<n; i++){
if(r[i] < c[i])
swap(r[i] ,c[i]);
rngs.push_back({c[i] ,-r[i]});
}
sort(rngs.begin() ,rngs.end());
int mx = -1;
for(auto&r : rngs) if(-r.second > mx){
po.push_back({r.first ,-r.second+1});
mx = -r.second;
}
po.insert(po.begin() ,make_pair(-1 ,0));
n = po.size();
vector <long long> dp(n ,1e18) ,exdp(n ,1e18);
dp[0] = 0 ,exdp[0] = 0;
while(k--){
swap(dp ,exdp);
hull h;
for(int i=1; i<n; i++){
h.add(-2*po[i].first ,exdp[i-1] + sqr(po[i].first) - sqr(max(0 ,po[i-1].second-po[i].first)));
dp[i] = sqr(po[i].second) + h.eval(po[i].second);
///for(int j=0; j<i; j++)
/// dp[i] = min(dp[i] ,exdp[j] + sqr(po[i].second-po[j+1].first+1) - sqr(max(0 ,po[j].second-po[j+1].first+1)));
}
}
return dp.back();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |