| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 871763 | LOLOLO | 휴가 (IOI14_holiday) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define f first
#define s second
#define pb push_back
#define ep emplace
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define mem(f,x) memset(f , x , sizeof(f))
#define sz(x) (int)(x).size()
#define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b))
#define mxx *max_element
#define mnn *min_element
#define cntbit(x) __builtin_popcountll(x)
#define len(x) (int)(x.length())
const int N = 8e5 + 100;
pair <ll, ll> seg[N];
int n;
void upd(int id, int l, int r, int x, int v, int add) {
if (l > x || r < x)
return;
if (l == r) {
seg[id].f += v;
seg[id].s += add;
return;
}
int m = (l + r) / 2;
upd(id * 2, l, m, x, v, add);
upd(id * 2 + 1, m + 1, r, x, v, add);
seg[id].f = seg[id * 2].f + seg[id * 2 + 1].f;
seg[id].s = seg[id * 2].s + seg[id * 2 + 1].s;
}
ll get(int id, int l, int r, ll cnt) {
if (seg[id].f <= cnt)
return seg[id].s;
if (l == r) {
return min((seg[id].s / seg[id].f) * cnt, seg[id].s);
}
int m = (l + r) / 2;
if (seg[id * 2 + 1].f >= cnt)
return get(id * 2 + 1, m + 1, r, cnt);
return get(id * 2, l, m, cnt - seg[id * 2 + 1].f) + seg[id * 2 + 1].s;
}
int L, R;
vector <int> v, rnk;
void move(int l, int r) {
while (L < l) {
upd(1, 0, n - 1, rnk[L], -1, -v[L]);
L++;
}
while (L > l) {
L--;
upd(1, 0, n - 1, rnk[L], 1, v[L]);
}
while (R < r) {
R++;
upd(1, 0, n - 1, rnk[R], 1, v[R]);
}
while (R > r) {
upd(1, 0, n - 1, rnk[R], -1, -v[R]);
R--;
}
}
ll cal(int v) {
if (v < 0)
return -1;
return get(1, 1, n, v);
}
void maximize(pair <ll, ll> &a, pair <ll, ll> b) {
if (a.f < b.f) {
a = b;
} else {
if (a.f == b.f) {
a.s = min(a.s, b.s);
}
}
}
void dnc(int st, int l1, int r1, int l, int r, vector <pair <ll, ll>> &f) {
if (l1 > r1 || st < 0)
return;
int m1 = (l1 + r1) / 2;
for (int i = l; i <= r; i++) {
move(min(st, i), max(st, i));
ll v = cal(m1 - abs(i - st));
maximize(f[m1], {v, abs(i - st)});
}
int opt = f[m1].s;
if (l >= st) {
dnc(st, l1, m1 - 1, l, opt + st, f);
dnc(st, m1 + 1, r1, opt + st, r, f);
} else {
dnc(st, m1 + 1, r1, l, st - opt, f);
dnc(st, l1, m1 - 1, st - opt, r, f);
}
}
ll findMaxAttraction(int _n, int st, int d, int att[]) {
n = _n;
map <int, int> mp;
int timer = 0;
for (int i = 0; i < n; i++) {
v.pb(att[i]);
mp[att[i]];
}
for (auto &x : mp) {
x.s = timer;
timer++;
}
for (auto x : v)
rnk.pb(mp[x]);
L = R = 0;
upd(1, 0, n - 1, rnk[L], 1, v[L]);
vector <pair <ll, ll>> d1(d + 1, {0, 0}), d2(d + 1, {0, 0});
dnc(st, 0, d, st, n - 1, d1);
dnc(st - 1, 0, d, 0, st - 1, d2);
ll ans = max(d1[d].f, d2[d].f);
for (int i = 0; i < d; i++) {
auto t = d1[i];
int v = t.s + 1;
if (v + i <= d) {
ans = max(ans, t.f + d2[d - v - i].f);
}
t = d2[i];
v = t.s + 1;
if (v + i <= d) {
ans = max(ans, t.f + d1[d - v - i].f);
}
}
return ans;
}