| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 158995 | crackersamdjam | Aliens (IOI16_aliens) | C++14 | 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>
#define gc getchar_unlocked()
#define pc(x) putchar_unlocked(x)
template<typename T> void scan(T &x){x = 0;register bool _=0;register T c=gc;_=c==45;c=_?gc:c;while(c<48||c>57)c=gc;for(;c<48||c>57;c=gc);for(;c>47&&c<58;c=gc)x=(x<<3)+(x<<1)+(c&15);x=_?-x:x;}
template<typename T> void printn(T n){register bool _=0;_=n<0;n=_?-n:n;char snum[65];int i=0;do{snum[i++]=n%10+48;n/= 10;}while(n);--i;if (_)pc(45);while(i>=0)pc(snum[i--]);}
template<typename First, typename ... Ints> void scan(First &arg, Ints&... rest){scan(arg);scan(rest...);}
template<typename T> void print(T n){printn(n);pc(10);}
template<typename First, typename ... Ints> void print(First arg, Ints... rest){printn(arg);pc(32);print(rest...);}
#define sq(x) (x)*(x)
#define peek(x) std::cout << #x << ' ' << x << std::endl
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
const int MM = 1e5+5;
const ld eps = 1e-12;
int n, q[MM], cnt[MM];
ld dp[MM];
vector<pii> a, b;
set<int> st;
bool cmp(const pii &x, const pii &y){
if(x.first != y.first)
return x.first < y.first;
return x.second > y.second;
}
ld eval(int l, int i){
//printf("eval %d %d %lld %lld\n", l, i, sq((ll)a[i].first - a[l+1].second + 1), -sq((ll)max(0, a[l].first - a[l+1].second + 1)));
//return dp[l] + sq((ll)a[i].first - a[l+1].second + 1) - sq((ll)max(0, a[l].first - a[l+1].second + 1));
//printf("eval %d %d %lld %lld\n", l, i, sq((ll)a[i].second - a[l+1].first + 1), -sq((ll)max(0, a[l].second - a[l+1].first + 1)));
return dp[l] + sq((ll)a[i].second - a[l+1].first + 1) - sq((ll)max(0, a[l].second - a[l+1].first + 1));
//dp[j] + (x[i] - y[j+1])^2 - (x[j] - y[j+1])^2
}
int inter(int i, int f, int s){
int l = i, m, r = n;
while(l <= r){
m = (l+r)/2;
if(eval(f, m) < eval(s, m))
l = m+1;
else
r = m-1;
}
//printf("inter %d %d = %d\n", f, s, l);
//find first when f gives higher (or equal)
//will never use f again
return l;
}
void run(ld cost, int K){
//printf("run %Lf\n", cost);
int l = 0, r = 0; q[0] = 0;
for(int i = 1; i <= n; i++){
//while(r-l >= 1 && i*(dp[q[l]] - dp[q[l+1]]) <= q[l] - q[l+1])
// l++;
//printf("compare %d, %Lf %Lf\n", r-l, eval(q[l], i), eval(q[l+1], i));
while(r-l >= 1 && (eval(q[l], i) >= eval(q[l+1], i))){
l++;
}
//peek(l);
dp[i] = eval(q[l], i) + cost;
cnt[i] = cnt[q[l]] + 1;
//printf("%d %Lf %d\n", i, dp[i], cnt[i]);
while(r-l >= 1 && inter(i, q[r-1], q[r]) >= inter(i, q[r], i)){
r--;
}
q[++r] = i;
}
//printf("res %Lf\n", dp[n]-cost*K);
}
long long take_photos(int Ln, int M, int K, int *R, int *C){
n = Ln;
for(int i = 0; i < n; i++){
if(R[i] < C[i])
swap(R[i], C[i]);
a.push_back({C[i], R[i]});
//flip
}
sort(a.begin(), a.end(), cmp);
/*
puts("a");
for(auto i: a)
print(i.first, i.second);
*/
//add filter to remove points with points top-right of it
for(int i = 0; i < a.size(); i++){
//print(a[i].first, a[i].second, -1);
if(st.lower_bound(a[i].second) == st.end())
b.push_back(a[i]);
st.insert(a[i].second);
}
a = b;
/*
puts("b");
for(auto i: a)
print(i.first, i.second);
puts("ok");
*/
n = a.size();
a.insert(a.begin(), {-1, -1});
//indexing
ld l = 0, m, r = 20;
while(r-l >= eps){
m = (l+r)/2;
run(m, K);
if(cnt[n] >= K)
l = m;
else
r = m;
}
run(r, K);
//cout << dp[n] << ' ' << r*K << ' ' << dp[n]-r*K << ' ' << round(dp[n]-r*K) << '\n';
return round(dp[n] - r*K);
}
#ifndef ONLINE_JUDGE
int main(){
int i1, i2, i3;
scan(i1, i2, i3);
int a1[i1], a2[i1];
for(int i = 0; i < i1; i++)
scan(a1[i], a2[i]);
print(take_photos(i1, i2, i3, a1, a2));
/*
int a1[] = {0, 4, 4, 4, 4}, a2[] = {3, 4, 6, 5, 6},
a3[] = {1, 4}, a4[] = {4, 1};
print(take_photos(5, 7, 2, a1, a2));
//print(take_photos(2, 6, 2, a3, a4));
*/
return 0;
}
#endif
/*
* n^2 k sol
* dp[k][i] = min{dp[k-1][j] + (x[i] - y[j+1])^2 - (x[j] - y[j+1])^2}
* (x is down, y is right)
*(max(0, x[j] - y[j+1]))^2 --may not need to subtract
*
* dp[j] + (x[i] - y[j+1])^2 - (x[j] - y[j+1])^2 <= dp[k] + (x[i] - y[k+1])^2 - (x[k] - y[k+1])^2 ; j < k
* dp[j] + (x[i] - y[j+1])^2 - (x[j] - y[j+1])^2 <= dp[k] + (x[i] - y[k+1])^2 - (x[k] - y[k+1])^2
*
* just bs :monkey:
*/
/*
* akvizna:
dp[i] = dp[j] + (i-j)/i + c
dp[j] + (i-j)/i <= dp[k] + (i-k)/i; j < k
dp[j]*i + (i-j) <= dp[k]*i + (i-k)
dp[j]*i - dp[k]*i <= j-k
i*(dp[j] - dp[k]) <= j-k
// can not divide the inequality bc. dp[j]-dp[k] may be neg., but intersect works because looking for equality
*/