This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
//template
#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define ALL(v) (v).begin(),(v).end()
using ll=long long int;
const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; const double eps=1e-12;
template<typename T>inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T>inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
//end
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
using P=pair<int,int>;
vector<P> pos,used;
rep(i,0,n){
if(r[i]>c[i])swap(r[i],c[i]);
pos.push_back({r[i],c[i]});
}
sort(ALL(pos),[](P& a,P& b){
if(a.first==b.first)return a.second>b.second;
else return a.first<b.first;
});
int mx=-1;
rep(i,0,n){
if(!chmax(mx,pos[i].second))continue;
used.push_back(pos[i]);
}
n=used.size();
int nxt=1;
ll from[510][510],to[510][510];
rep(i,0,n+5)rep(j,0,k+5)from[i][j]=INF;
from[0][0]=0;
for(auto& p:used){
rep(i,0,n+5)rep(j,0,k+5)to[i][j]=INF;
rep(i,0,n+5)rep(j,0,k+1)if(from[i][j]!=INF){
if(p!=used.back()){
chmin(to[i][j],from[i][j]);
}
ll add=1LL*(p.second-used[i].first+1)*(p.second-used[i].first+1);
if(i)add-=max(0LL,1LL*(used[i].first-used[i-1].second+1)*(used[i].first-used[i-1].second+1));
chmin(to[nxt][j+1],from[i][j]+add);
}
swap(from,to);
nxt++;
}
ll res=INF;
rep(j,1,k+1)chmin(res,from[n][j]);
return res;
}
/*
int main() {
int n, m, k;
assert(3 == scanf("%d %d %d", &n, &m, &k));
std::vector<int> r(n), c(n);
for (int i = 0; i < n; i++) {
assert(2 == scanf("%d %d", &r[i], &c[i]));
}
long long ans = take_photos(n, m, k, r, c);
printf("%lld\n", ans);
return 0;
}
//*/
# | 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... |