이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;
const long long inf=1e13;
long long dp[MAXN];
int cnt[MAXN];
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];
int n,m,k,sz;
long long area(long long l,long long r){
if(l>r)return 0;
return (r-l+1)*(r-l+1);
}
long long cost(int l,int r){
return area(w[l].l,w[r].r) - area(w[l].l,w[l-1].r);
}
void solve(long long delta){
for(int i=1;i<=sz;i++){
dp[i]=inf;
for(int t=i;t>=1;t--){
if(dp[t-1]+cost(t,i)+delta<dp[i]){
dp[i]=dp[t-1]+cost(t,i)+delta;
cnt[i]=cnt[t-1]+1;
}else if(dp[t-1]+cost(t,i)+delta==dp[i] and cnt[t-1]+1<cnt[i]){
cnt[i]=cnt[t-1]+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(l+1);
return dp[sz]-cnt[sz]*(l+1);
}
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];
}
return bin();
}
/*int main(){
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... |