| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 209742 | the_art_of_war | 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.
//
// Created by Ильдар Ялалов on 14.01.2020.
//
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf_int = 1e9 + 100;
const ll inf_ll = 1e18;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double dbl;
typedef unsigned int uint;
#define pb push_back
#define eb emplace_back
const double pi = 3.1415926535898;
#define dout if(debug) cout
#define fi first
#define se second
#define sp setprecision
#define sz(a) (int(a.size()))
#define mp make_pair
#define all(a) a.begin(),a.end()
//region debug
template<class T1, class T2>
std::ostream &operator<<(std::ostream &out, const std::pair<T1, T2> &rhs) {
out << "( " << rhs.first << " , " << rhs.second << " )";
return out;
}
template<typename A, typename B>
string to_string(pair<A, B> p);
template<typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
template<typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string &s) {
return '"' + s + '"';
}
string to_string(const char *s) {
return to_string((string) s);
}
string to_string(bool b) {
return (b ? "true" : "false");
}
string to_string(vector<bool> v) {
bool first = true;
string res = "{";
for (int i = 0; i < static_cast<int>(v.size()); i++) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(v[i]);
}
res += "}";
return res;
}
template<size_t N>
string to_string(bitset<N> v) {
string res = "";
for (size_t i = 0; i < N; i++) {
res += static_cast<char>('0' + v[i]);
}
return res;
}
template<typename A>
string to_string(A v) {
bool first = true;
string res = "{";
for (const auto &x : v) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(x);
}
res += "}";
return res;
}
template<typename A>
string to_string(vector<vector<A>> v) {
bool first = true;
string res = "{";
for (const auto &x : v) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(x);
res += "\n";
}
res += "}";
return res;
}
template<typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template<typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
template<typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " +
to_string(get<3>(p)) + ")";
}
void debug_out() { cerr << endl; }
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
debug_out(T...);
}
//endregion
#ifdef zxc1
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
bool debug = 0;
const int MAXN = 1e6 + 100;
const int LOG = 21;
const int mod = 1e9 + 7;
const int MX = (2e7 + 100);
struct Point {
ll a;
ll b;
int cnt;
Point() {
a = b = 0;
}
};
struct vertex_lichao {
int l, r;
Point p;
vertex_lichao() {
l = r = 0;
}
vertex_lichao(Point &P) {
l = r = 0;
p = P;
}
};
inline pair<ll, int> get(const Point &cur, ll x) {
return {cur.a + x * cur.b, cur.cnt};
}
vector<pii> good;
pair<ll, ll> dp[MAXN];
vector<Point> hull;
bool ccw(Point a, Point b, Point c) {
return (long double)a.b * (b.a - c.a) + (long double)b.b * (c.a - a.a) + (long double)c.b * (a.a - b.a) >= 1e-9;
}
void add_point(Point &p) {
while (sz(hull) >= 2 && !ccw(hull[sz(hull) - 2], hull[sz(hull) - 1], p)) {
hull.pop_back();
}
hull.push_back(p);
}
int top = 0;
pair<ll, int> get_best(ll x) {
top = min(top, sz(hull) - 1);
while (top + 1 < sz(hull) && get(hull[top], x) >= get(hull[top + 1], x)) {
top++;
}
return get(hull[top], x);
}
pll get_solve(ll cost) {
pair<ll, int> prev = {0, 0};
debug(cost);
top = 0;
hull.clear();
for (int i = 0; i < sz(good); ++i) {
ll spec = 0;
int x = good[i].fi;
int y = good[i].se;
if (i > 0 && good[i - 1].se >= x) {
spec = good[i - 1].se - x + 1;
spec = spec * spec;
}
debug(spec);
Point add;
add.a = prev.fi + 1ll * x * x - spec;
add.b = -2 * x;
add.cnt = prev.se;
add_point(add);
debug(i);
for (auto x : hull) {
debug(x.a, x.b, x.cnt);
}
auto val = get_best(y + 1);
val.first += 1ll * (y + 1) * (y + 1);
val.se++;
val.first += cost;
dp[i] = val;
prev = dp[i];
debug(i, dp[i]);
}
return prev;
}
void solve() {
int n, m, k;
cin >> n >> m >> k;
vector<pii> all_c;
for (int i = 1; i <= n; ++i) {
int r, c;
cin >> r >> c;
if (c < r)
swap(r, c);
all_c.pb({r, c});
}
sort(all(all_c));
map<int, int> mp;
for (auto x : all_c) {
mp[x.fi] = x.se;
}
int mx = -1;
for (auto x : mp) {
if (mx >= x.se) {
continue;
}
good.push_back(x);
mx = max(mx, x.se);
}
debug(all_c);
debug(good);
ll l = 0, r = 1e13;
pair<ll, int> last;
ll cost = -1;
while (l <= r) {
ll mid = (l + r) >> 1;
auto x = get_solve(mid);
if (x.se <= k) {
if (cost == -1 || mid <= cost) {
last = x;
cost = mid;
}
r = mid - 1;
} else {
l = mid + 1;
}
}
assert(cost != -1);
cout << last.fi - cost * k << "\n";
}
// CHECK LIMITS (n <= 10^5)
// CHECK CORNER CASES ( n==1)
signed main() {
#ifdef zxc
freopen("../input.txt", "r", stdin);
// freopen("../output.txt", "w", stdout);
#else
#endif //zxc
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cout.setf(ios::fixed);
cout.precision(15);
int t = 1;
while (t--)
solve();
debug(1.0 * clock() / CLOCKS_PER_SEC);
}