이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef pair<ld, ld> dd;
typedef pair<ii, ll> pi;
#define MAXN 1001001
ll N, M, K, vn;
int mx[MAXN], cnt[MAXN];
ll dp[MAXN];
vector<ii> v;
vector<pi> hal;
ll ccw(ii A, ii B, ii C)
{
return A.X * (B.Y - C.Y) + B.X * (C.Y - A.Y) + C.X * (A.Y - B.Y);
}
ll solve(ll x)
{
hal.clear();
for (int i = 0; i < vn; i++) {
ll ix = -2 * (v[i].X - 1);
ll iy = dp[i] + (v[i].X - 1) * (v[i].X - 1) - (i ? max(0LL, v[i - 1].Y + 1 - v[i].X) * max(0LL, v[i - 1].Y + 1 - v[i].X) : 0);
while (hal.size() > 1 && ccw(hal[hal.size() - 2].X, hal.back().X, {ix, iy}) >= 0) hal.pop_back();
hal.pb({{ix, iy}, i});
int lo = 0, hi = hal.size() - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (hal[mid].X.X * v[i].Y + hal[mid].X.Y > hal[mid + 1].X.X * v[i].Y + hal[mid + 1].X.Y)
lo = mid + 1;
else
hi = mid;
}
//for (pi j: hal) cout << j.X.X * v[i].Y + j.X.Y << '.'<<j.Y<<' ';cout<<endl;
dp[i + 1] = hal[lo].X.X * v[i].Y + hal[lo].X.Y + x + v[i].Y * v[i].Y;
cnt[i + 1] = 1 + cnt[hal[lo].Y];
}
return cnt[vn];
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
memset(mx, -1, sizeof mx);
N = n; M = m; K = k;
for (int i = 0; i < n; i++) {
if (r[i] > c[i]) {
swap(r[i], c[i]);
}
}
for (int i = 0; i < n; i++) {
mx[r[i]] = max(mx[r[i]], c[i]);
}
int cu = -1;
for (int i = 0; i <= m; i++) {
if (mx[i] > cu) {
cu = mx[i];
v.pb({i, cu});
}
}
vn = v.size();
//for (int i = 0; i < vn; i++) cout << v[i].X <<' ' << v[i].Y<<endl;
ll lo = 0, hi = M * M;
while (lo < hi) {
ll mid = (lo + hi) / 2;
if (solve(mid) > K)
lo = mid + 1;
else
hi = mid;
}//cout<<lo<<' '<<dp[vn]<<' '<<cnt[vn]<<endl;
solve(lo);
return dp[vn] - lo * K;
}
# | 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... |