| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 32181 | dongwon0427 | Aliens (IOI16_aliens) | C++98 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,ld> pil;
struct _tuple {
int x,y;
};
_tuple A[100005],B[100005];
int n;
ld dp[100005];
int gaesu[100005];
pil CHT(ld c) {
gaesu[0]=0;
for(int i=1;i<=n;i++) {
dp[i] = (ld)(A[i].y-A[1].x+1)*(ld)(A[i].y-A[1].x+1)-c;
int minidx = 0;
for(int j=1;j<i;j++) {
if( dp[i] > dp[j] + (ld)(A[i].y-A[j+1].x+1)*(ld)(A[i].y-A[j+1].x+1) - (ld)max(0,-A[j+1].x+A[j].y+1)*(ld)max(0,-A[j+1].x+A[j].y+1) - c ) {
minidx = j;
dp[i] = dp[j] + (ld)(A[i].y-A[j+1].x+1)*(ld)(A[i].y-A[j+1].x+1) - (ld)max(0,-A[j+1].x+A[j].y+1)*(ld)max(0,-A[j+1].x+A[j].y+1) - c;
}
}
gaesu[i] = gaesu[minidx]+1;
}
//cout<<c<<" : "<<dp[n]<<' '<<gaesu[n]<<endl;
return pil(gaesu[n],dp[n]);
}
ll take_photos(int N, int m, int k, std::vector<int> r, std::vector<int> c) {
for(int i=0;i<N;i++) {
B[i].x=r[i];
B[i].y=c[i];
if(B[i].x > B[i].y) swap(B[i].x,B[i].y);
}
sort(B,B+N,[](_tuple a,_tuple b){return a.x>b.x;});
for(int i=0;i<N;i++) {
while(n!=0 && A[n].y <= B[i].y) {
n--;
}
A[++n] = B[i];
}
reverse(A+1,A+1+n);
if(k>n) k = n;
ll bs = -(ll)m*(ll)m-1ll, be = 0;
int lft=1,rht=n;
ll L=(ll)m*(ll)m,R=(ll)m*(ll)m;
while(bs<=be) {
ll bm = (bs+be)/2;
//printf("%d\n",bm);
ld gi = (ld)bm + (ld)0.5;
pil tmp = CHT(gi);
if(tmp.first==k) {
return (long long)(tmp.second + gi*(ld)(k));
}
if(tmp.first > k) {
be=bm-1;
if(rht >= tmp.first) {
rht = tmp.first;
R = (ll)(tmp.second + gi*(ld)(k));
}
} else {
bs=bm+1;
if(lft <= tmp.first) {
lft = tmp.first;
R = (ll)(tmp.second + gi*(ld)(k));
}
}
}
/*for(ll i=bs;i<=be;i++) {
CHT((ld)i+(ld)0.5);
}*/
return (L*(ll)(rht-k) + R*(ll)(k-lft)) / (ll)(-lft+rht);
}