이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#pragma GCC target("sse,sse2,sse3,ssse3,abm,avx2")
#include <bits/stdc++.h>
using namespace std;
#ifndef WAIMAI
#include "aliens.h"
#endif
#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif
#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second
const int SIZE = 1e5 + 5;
int n, k;
pair<int, int> p[SIZE];
pair<ll, int> dp;
deque<tuple<int, ll, int>> st;
pair<ll, int> cal(tuple<int, ll, int> f, int x) {
return {1ll * get<0>(f) * x + get<1>(f), get<2>(f) + 1};
}
bool del(tuple<int, ll, int> L1, tuple<int, ll, int> L2, tuple<int, ll, int> L) {
auto [M1, K1, c1] = L1;
auto [M2, K2, c2] = L2;
auto [M, K, c] = L;
return make_pair((K - K1) * (M1 - M2), c) <= make_pair((K2 - K1) * (M1 - M), c2);
}
bool ok(ll pen) {
st.clear();
st.pb(-2 * p[1].F, 1ll * p[1].F * p[1].F, 0);
FOR (i, 1, n) {
while (st.size() >= 2 && cal(st[0], p[i].S) >= cal(st[1], p[i].S)) st.pop_front();
dp = cal(st[0], p[i].S);
dp.F += 1ll * p[i].S * p[i].S + pen;
if (i == n) break;
tuple<int, ll, int> val = {-2 * p[i + 1].F, dp.F + 1ll * p[i + 1].F * p[i + 1].F - (p[i].S > p[i + 1].F ? 1ll * (p[i].S - p[i + 1].F) * (p[i].S - p[i + 1].F) : 0), dp.S};
while (st.size() >= 2 && del(st.end()[-2], st.back(), val)) st.pop_back();
st.pb(val);
}
return dp.S <= k;
}
ll take_photos(int _n, int m, int _k, vector<int> _r, vector<int> _c) {
n = _n, k = _k;
FOR (i, 0, n - 1) {
if (_r[i] > _c[i]) swap(_r[i], _c[i]);
p[i + 1] = {_r[i], _c[i] + 1};
}
sort(p + 1, p + n + 1, [&](auto l, auto r) {
return l.F != r.F ? l.F < r.F : l.S > r.S;
});
int sz = 0;
FOR (i, 1, n) if (sz == 0 || p[i].S > p[sz].S) p[++sz] = p[i];
n = sz;
ll l = 0, r = 1ll * m * m;
while (l < r) {
ll mid = (l + r) / 2;
if (ok(mid)) r = mid;
else l = mid + 1;
}
ok(l);
return dp.F - 1ll * k * l;
}
/*
in1
5 7 2
0 3
4 4
4 6
4 5
4 6
out1
25
in2
2 6 2
1 4
4 1
out2
16
*/
#ifdef WAIMAI
int main() {
int n, m, k;
assert(3 == scanf("%d %d %d", &n, &m, &k));
vector<int> r(n), c(n);
for (int i = 0; i < n; i++) {
assert(2 == scanf("%d %d", &r[i], &c[i]));
}
ll ans = take_photos(n, m, k, r, c);
printf("%lld\n", ans);
return 0;
}
#endif
# | 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... |