#include"aliens.h" #include<bits/stdc++.h> using namespace std; const int MAXN=1e5+5; const long long INF=2e18; pair<long long,long long> dp[MAXN],line[MAXN]; double range[MAXN]; long long st[MAXN],ed[MAXN]; int pos[MAXN]; stack<int> ss; double intersect(pair<long long,long long> a,pair<long long,long long> b) { return (double)(b.second-a.second)/(a.first-b.first); } void solve(int n,long long cost) { int cnt=0; dp[0]={0,0},range[0]=-INF; for(int i=1;i<=n;i++) { dp[i]={(ed[i]-st[1]+1)*(ed[i]-st[1]+1)+cost,1}; if(!ss.empty()) { int pp=upper_bound(range,range+cnt+1,ed[i]+1)-range-1; for(int j=max(0,pp-1),p=pos[j];j<=min(cnt,pp+1);p=pos[++j]) dp[i]=min(dp[i],{(ed[i]+1)*(ed[i]+1+line[p].first)+cost+line[p].second,dp[p].second+1}); } line[i]={-st[i+1]*2,dp[i].first+st[i+1]*st[i+1]-max(0LL,ed[i]-st[i+1]+1)*max(0LL,ed[i]-st[i+1]+1)}; while(!ss.empty()&&range[cnt]>intersect(line[i],line[ss.top()])) ss.pop(),cnt--; if(!ss.empty()) range[++cnt]=intersect(line[i],line[ss.top()]),range[cnt+1]=INF; pos[cnt]=i,ss.push(i); } while(!ss.empty()) ss.pop(); } long long take_photos(int n,int m,int k,vector<int> R,vector<int> C) { vector< pair<int,int> > vi; for(int i=0;i<n;i++) vi.push_back({min(R[i],C[i]),max(R[i],C[i])}); sort(vi.begin(),vi.end()); vector< pair<int,int> > vv; vv.push_back(vi[0]); for(int i=1;i<n;i++) { if(vv.back().first==vi[i].first) vv.pop_back(),vv.push_back(vi[i]); else if(vv.back().second<vi[i].second) vv.push_back(vi[i]); } n=vv.size(),k=min(k,n); for(int i=1;i<=n;i++) st[i]=vv[i-1].first,ed[i]=vv[i-1].second; long long l=0,r=1e13,pos=0; while(l<=r) { long long mid=(l+r)/2; solve(n,mid); if(dp[n].second<=k) r=mid-1,pos=mid; else l=mid+1; } solve(n,pos); return dp[n].first-dp[n].second*pos; }

aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~