이 제출은 이전 버전의 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>
#include "aliens.h"
using namespace std;
#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;
}
# | 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... |