| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 575380 | handlename | Aliens (IOI16_aliens) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
const int MOD=1e9+7;
struct convex{
deque<pair<long long,long long> > dq;
long long f(pair<long long,long long> line, long long x){
return line.first*x + line.second;
}
long long qry(long long x){
/*
long long res=1e18;
for (auto i:dq) res=min(res,f(i,x));
return res;
*/
while(dq.size()>1){
if(f(dq[0],x)>f(dq[1],x)){ //the next line is better
dq.pop_front(); //remove useless line
}
else break;
}
return f(dq[0],x);
}
long double intersect(long long m1, long long c1, long long m2, long long c2){
return (long double)(c2-c1)/(m1-m2);
}
long double intersect(pair<long long,long long> p1, pair<long long,long long> p2){
return intersect(p1.first,p1.second,p2.first,p2.second);
}
void ins(long long m,long long c) {//insert line y=mx+c
pair<long long,long long> line = make_pair(m,c);
while (dq.size()>1) { //to prevent seg fault
long long s = dq.size();
if (intersect(dq[s-1], line) <= intersect(dq[s-2], line)){
dq.pop_back(); //removes useless line
}
else break;
}
dq.push_back(line);
}
} *conv;
pair<int,int> brr[200001];
vector<pair<long long,long long> > arr;
long long take_photos(int n,int m,int k,vector<int> r,vector<int> c){
for (int i=0;i<n;i++){
r[i]++;
c[i]++;
if (r[i]>c[i]) swap(r[i],c[i]); //ri<=ci
brr[i].first=r[i];
brr[i].second=c[i];
}
sort(brr,brr+n);
arr.pb(mp(0,0));
for (int i=0;i<n;i++){
while (!arr.empty() && arr.back().first==brr[i].first){
arr.pop_back();
}
if (arr.empty() || brr[i].second>arr.back().second){
arr.pb(brr[i]);
}
}
n=arr.size()-1;
for (int i=1;i<=n;i++){
//cout<<arr[i].first<<' '<<arr[i].second<<'\n';
}
long long dp[k+1][n+1];
conv=new convex();
dp[0][0]=0;
for (int j=1;j<=n;j++){
dp[0][j]=1e18;
}
for (int i=1;i<=k;i++){
dp[i][0]=0;
for (int j=1;j<=n;j++){
dp[i][j]=dp[i-1][j];
for (int x=1;x<j;x++){
//take square from x to j
//square is (rx,rx) to (cj,cj)
long long cur=0;
cur+=dp[i-1][x-1];
cur+=(arr[j].second-arr[x].first+1)*(arr[j].second-arr[x].first+1);
dp[i][j]=min(dp[i][j],cur);
}
dp[i][j]=min(dp[i][j],dp[i-1][j-1]+(arr[j].second-arr[j].first+1)*(arr[j].second-arr[j].first+1));
//cout<<i<<' '<<j<<' '<<dp[i][j]<<'\n';
}
}
return dp[k][n];
}
void runtc(){
int n,m,k;
cin>>n>>m>>k;
vector<int> r,c;
for (int i=0;i<n;i++){
int x,y;
cin>>x>>y;
r.pb(x);
c.pb(y);
}
cout<<take_photos(n,m,k,r,c);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
freopen("input1.in","r",stdin);
//freopen("output1.out","w",stdout);
int tc;
//cin>>tc;
tc=1;
for (int i=1;i<=tc;i++){
//cout<<"Case #"<<i<<": ";
runtc();
}
}