#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;
const long long inf=1e13,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 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;
for(int t=i;t>=1;t--){
long long s=(long long) dp[t-1] + bonus[t] + w[i].r*(w[i].r+2) - 2*w[i].r*w[t].l + w[t].l*(w[t].l-2) + delta + 1;
if(s<dp[i]){
dp[i]=s; cnt[i]=cnt[t-1]+1;
}else if(s==dp[i]){
cnt[i]=min(cnt[i],cnt[t-1]+1);
}
}
/*hull.addline({-2*w[i].l,coef(i),0,cnt[i-1]});
pair<long long,int> curr=hull.query(w[i].r);
dp[i]=curr.first+w[i].r*(w[i].r+2)+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]=(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;
}*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2384 KB |
Correct answer: answer = 4 |
2 |
Correct |
1 ms |
2384 KB |
Correct answer: answer = 4 |
3 |
Correct |
1 ms |
2384 KB |
Correct answer: answer = 4 |
4 |
Incorrect |
1 ms |
2384 KB |
Wrong answer: output = 14, expected = 12 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2384 KB |
Correct answer: answer = 1 |
2 |
Correct |
1 ms |
2384 KB |
Correct answer: answer = 4 |
3 |
Correct |
1 ms |
2384 KB |
Correct answer: answer = 1 |
4 |
Correct |
1 ms |
2384 KB |
Correct answer: answer = 5 |
5 |
Correct |
1 ms |
2384 KB |
Correct answer: answer = 41 |
6 |
Correct |
1 ms |
2384 KB |
Correct answer: answer = 71923 |
7 |
Correct |
2 ms |
2384 KB |
Correct answer: answer = 77137 |
8 |
Correct |
8 ms |
2384 KB |
Correct answer: answer = 764 |
9 |
Correct |
11 ms |
2384 KB |
Correct answer: answer = 250000 |
10 |
Correct |
11 ms |
2384 KB |
Correct answer: answer = 500 |
11 |
Correct |
1 ms |
2384 KB |
Correct answer: answer = 32 |
12 |
Correct |
10 ms |
2512 KB |
Correct answer: answer = 130050 |
13 |
Correct |
11 ms |
2384 KB |
Correct answer: answer = 5110 |
14 |
Correct |
4 ms |
2384 KB |
Correct answer: answer = 2626 |
15 |
Correct |
4 ms |
2676 KB |
Correct answer: answer = 796 |
16 |
Correct |
11 ms |
2384 KB |
Correct answer: answer = 7580 |
17 |
Correct |
11 ms |
2512 KB |
Correct answer: answer = 1904 |
18 |
Correct |
7 ms |
2384 KB |
Correct answer: answer = 996004 |
19 |
Correct |
7 ms |
2556 KB |
Correct answer: answer = 38817 |
20 |
Correct |
7 ms |
2384 KB |
Correct answer: answer = 4096 |
21 |
Correct |
1 ms |
2384 KB |
Correct answer: answer = 1 |
22 |
Correct |
1 ms |
2384 KB |
Correct answer: answer = 1 |
23 |
Correct |
11 ms |
2384 KB |
Correct answer: answer = 2040 |
24 |
Correct |
1 ms |
2384 KB |
Correct answer: answer = 2 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2384 KB |
Correct answer: answer = 4 |
2 |
Correct |
1 ms |
2384 KB |
Correct answer: answer = 4 |
3 |
Correct |
1 ms |
2384 KB |
Correct answer: answer = 4 |
4 |
Incorrect |
1 ms |
2384 KB |
Wrong answer: output = 14, expected = 12 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2384 KB |
Correct answer: answer = 4 |
2 |
Correct |
1 ms |
2384 KB |
Correct answer: answer = 4 |
3 |
Correct |
1 ms |
2384 KB |
Correct answer: answer = 4 |
4 |
Incorrect |
1 ms |
2384 KB |
Wrong answer: output = 14, expected = 12 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2384 KB |
Correct answer: answer = 4 |
2 |
Correct |
1 ms |
2384 KB |
Correct answer: answer = 4 |
3 |
Correct |
1 ms |
2384 KB |
Correct answer: answer = 4 |
4 |
Incorrect |
1 ms |
2384 KB |
Wrong answer: output = 14, expected = 12 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2384 KB |
Correct answer: answer = 4 |
2 |
Correct |
1 ms |
2384 KB |
Correct answer: answer = 4 |
3 |
Correct |
1 ms |
2384 KB |
Correct answer: answer = 4 |
4 |
Incorrect |
1 ms |
2384 KB |
Wrong answer: output = 14, expected = 12 |
5 |
Halted |
0 ms |
0 KB |
- |