이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;
const long long inf=1e12,inff=1e18;
struct interval{
int l,r;
inline friend bool operator < (interval fr,interval sc){
if(fr.l==sc.l)return fr.r>sc.r;
return fr.l<sc.l;
}
}s[MAXN],w[MAXN];
struct line{
long long a,b,from;
int cnt;
long long val(long long x){
return a*x+b;
}
};
bool smaller(line fr,line sc,long long x){
if(fr.val(x)<sc.val(x))return true;
if(fr.val(x)==sc.val(x) and fr.cnt<sc.cnt)return true;
return false;
}
long long intersec(line fr,line sc){
long long x=(fr.b-sc.b)/(sc.a-fr.a);
if(smaller(fr,sc,x+1))x++;
if(!smaller(fr,sc,x))x--;
return x;
}
struct CHT{
deque<line> d;
void init(){
d.clear();
}
void addline(line s){
while(!d.empty() and smaller(s,d.back(),d.back().from))d.pop_back();
if(d.empty()){
d.push_back({s.a,s.b,-inf,s.cnt});
}else{
d.push_back({s.a,s.b,intersec(s,d.back()),s.cnt});
}
}
pair<long long,int> query(long long x){
while(d.size()>1 and x>=d[1].from){
d.pop_front();
}
return {d.front().val(x),d.front().cnt};
}
}hull;
int n,m,k,sz;
long long bonus[MAXN];
long long dp[MAXN];
int cnt[MAXN];
long long coef(int id){
return (long long) -bonus[id] + dp[id-1] + w[id].l*(w[id].l-2);
}
void solve(long long delta){
hull.init();
for(int i=1;i<=sz;i++){
dp[i]=inff;
hull.addline({-2*w[i].l,coef(i),0,cnt[i-1]});
pair<long long,int> curr=hull.query(w[i].r);
dp[i]=(long long) curr.first+w[i].r*(w[i].r+2)+delta+1;
cnt[i]=curr.second+1;
}
}
long long bin(){
long long l=-1,r=inf,tt;
while(l+1<r){
tt=(l+r)/2;
solve(tt);
if(cnt[sz]>k){
l=tt;
}else{
r=tt;
}
}
solve(r);
if(cnt[sz]==k)return dp[sz]-cnt[sz]*r;
long long val2=dp[sz]-cnt[sz]*r;
int k2=cnt[sz];
solve(r-1);
long long val1=dp[sz]-cnt[sz]*(r-1);
int k1=cnt[sz];
return (long long) val1 + (k-k1)*(val2-val1)/(k2-k1);
}
long long 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++){
s[i]={min(r[i-1],c[i-1])+1,max(r[i-1],c[i-1])+1};
}
sort(s+1,s+n+1);
for(int i=1;i<=n;i++){
if(sz>0 and s[i].r<=w[sz].r)continue;
sz++; w[sz]=s[i];
}
for(int i=1;i<=sz;i++){
if(w[i-1].r>=w[i].l)bonus[i]=(long long) (w[i-1].r-w[i].l+1)*(w[i-1].r-w[i].l+1);
}
k=min(k,sz);
return bin();
}
/*int main(){
hull.init();
cout<<take_photos(5, 7, 2, {0, 4, 4, 4, 4}, {3, 4, 6, 5, 6})<<"\n";
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... |