#include "aliens.h" #include <bits/stdc++.h> using namespace std; struct cell { long long int a,b,mi,ma; }; struct line { long double a,b; int ind; }; bool cmp(cell a1,cell a2) { if(a1.a!=a2.a)return a1.a<a2.a; return a1.b>a2.b; } long double get_value(line a,long long int x) { return a.a*x+a.b; } long double intersect(line a1,line a2) { if(a1.a==a2.a) { cout<<"!!!!!!!!!!!!"<<a1.a<<" "<<a2.a<<endl; exit(0); } return (a1.b-a2.b)/(a2.a-a1.a); } cell g[100005]; long long int n,m,k,dp[100005],use[100005],br; cell c[100005]; vector<line>v; void clea() { int to=-1; for(int i=1;i<=n;i++) { if(to<max(g[i].a,g[i].b)) { to=max(g[i].a,g[i].b); br++; c[br]=g[i]; } } } void add(line c) { line top; while(v.size()>=2) { top=v.back(); v.pop_back(); if(intersect(v.back(),top)<intersect(v.back(),c)) { v.push_back(top); break; } } v.push_back(c); } void make_dp(long long int cost) { v.clear(); int to=0; line g; add({c[1].mi*-2,c[1].mi*c[1].mi-2*c[1].mi+1,0}); for(int i=1;i<=br;i++) { while(to<v.size()-1&&get_value(v[to],c[i].ma)>=get_value(v[to+1],c[i].ma))to++; dp[i]=v[to].b+v[to].a*c[i].ma+c[i].ma*c[i].ma+2*c[i].ma+cost; //cout<<v[to].a<<" "<<v[to].b<<" "<<dp[i]<<endl; use[i]=use[v[to].ind]+1; if(i==br)break; g.b=dp[i]+c[i+1].mi*c[i+1].mi-2*c[i+1].mi+1-max(0ll,c[i].ma-c[i+1].mi+1)*max(0ll,c[i].ma-c[i+1].mi+1); g.a=-2*c[i+1].mi; g.ind=i; add(g); } } long long int take_photos(int N, int M, int K, vector<int> R, vector<int> C) { n=N; m=M; k=K; for(int i=1;i<=n;i++) { g[i].a=R[i-1]; g[i].b=C[i-1]; g[i].mi=min(g[i].a,g[i].b); g[i].ma=max(g[i].a,g[i].b); } sort(g+1,g+n+1,cmp); clea(); k=min(k,br); long long int l=1,r=1e12,mid; while(l<=r) { mid=(l+r)/2; make_dp(mid); if(use[br]>k)l=mid+1; else r=mid-1; } //cout<<endl<<endl; make_dp(l); //cout<<endl; //cout<<l<<" "<<use[br]<<" "<<dp[br]<<endl; return dp[br]-k*l; }

aliens.cpp: In function 'void make_dp(long long int)':
aliens.cpp:68:17: warning: narrowing conversion of '(c[1].cell::mi * -2)' from 'long long int' to 'long double' [-Wnarrowing]
   68 |     add({c[1].mi*-2,c[1].mi*c[1].mi-2*c[1].mi+1,0});
      |          ~~~~~~~^~~
aliens.cpp:68:46: warning: narrowing conversion of '(((c[1].cell::mi * c[1].cell::mi) - (2 * c[1].cell::mi)) + 1)' from 'long long int' to 'long double' [-Wnarrowing]
   68 |     add({c[1].mi*-2,c[1].mi*c[1].mi-2*c[1].mi+1,0});
      |                     ~~~~~~~~~~~~~~~~~~~~~~~~~^~
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
      |         ^~~~