結果
| 問題 | No.3583 二部マッチング最適化 |
| コンテスト | |
| ユーザー |
👑  potato167
|
| 提出日時 | 2026-07-04 17:33:41 |
| 言語 | C++17 (gcc 15.2.0 + boost 1.90.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 9,471 bytes |
| 記録 | |
| コンパイル時間 | 1,699 ms |
| コンパイル使用メモリ | 230,236 KB |
| 実行使用メモリ | 6,528 KB |
| 最終ジャッジ日時 | 2026-07-04 17:33:53 |
| 合計ジャッジ時間 | 2,946 ms |
|
ジャッジサーバーID （参考情報） |
judge1_1 / judge2_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 43 RE * 1 |
ソースコード
// https://uoj.ac/submission/769553
#line 1 "b.cpp"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll ILL=2167167167167167167;
const int INF=2100000000;
#define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
#define all(p) p.begin(),p.end()
template<class T> using _pq = priority_queue<T, vector<T>, greater<T>>;
template<class T> int LB(vector<T> &v,T a){return lower_bound(v.begin(),v.end(),a)-v.begin();}
template<class T> int UB(vector<T> &v,T a){return upper_bound(v.begin(),v.end(),a)-v.begin();}
template<class T> bool chmin(T &a,T b){if(b<a){a=b;return 1;}else return 0;}
template<class T> bool chmax(T &a,T b){if(a<b){a=b;return 1;}else return 0;}
template<class T> void So(vector<T> &v) {sort(v.begin(),v.end());}
template<class T> void Sore(vector<T> &v) {sort(v.begin(),v.end(),[](T x,T y){return x>y;});}
bool yneos(bool a,bool upp=false){if(a){cout<<(upp?"YES\n":"Yes\n");}else{cout<<(upp?"NO\n":"No\n");}return a;}
template<class T> void vec_out(vector<T> &p,int ty=0){
if(ty==2){cout<<'{';for(int i=0;i<(int)p.size();i++){if(i){cout<<",";}cout<<'"'<<p[i]<<'"';}cout<<"}\n";}
else{if(ty==1){cout<<p.size()<<"\n";}for(int i=0;i<(int)(p.size());i++){if(i) cout<<" ";cout<<p[i];}cout<<"\n";}}
template<class T> T vec_min(vector<T> &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmin(ans,x);return ans;}
template<class T> T vec_max(vector<T> &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmax(ans,x);return ans;}
template<class T> T vec_sum(vector<T> &a){T ans=T(0);for(auto &x:a) ans+=x;return ans;}
int pop_count(long long a){int res=0;while(a){res+=(a&1),a>>=1;}return res;}
template<class T> T square(T a){return a * a;}
namespace po167{
struct UF
{
using _F = int;
int _n;
std::vector<_F> wei;
std::vector<int> q;
int component;
UF(int n):_n(n), wei(n), component(n), par(n){
for (int i = 0; i < n; i++){
wei[i] =1, par[i] = i;
}
}
void intialize(){
for (auto x : q){
wei[root(x)] = 1;
par[x] = x;
}
component = (int)par.size();
q = {};
}
//根っこを返す
int root(int a){
assert(0 <= a && a < _n);
if (a == par[a]) return a;
return par[a] = root(par[a]);
}
//trueなら1,falseなら0
int same(int a, int b){
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
if(root(a) == root(b)) return 1;
else return 0;
}
_F size(int a){
return wei[root(a)];
}
//a,bが違う根っこの元なら結合する,結合したらtrueを返す
bool unite(int a,int b){
a = root(a), b = root(b);
if (a == b) return false;
par[b] = a;
q.push_back(b);
wei[a] += wei[b];
component--;
return true;
}
private:
std::vector<int> par;
};
}
using po167::UF;
#include <algorithm>
#include <cassert>
#include <functional>
#include <vector>
#ifdef _MSC_VER
#include <intrin.h>
#endif
#if __cplusplus >= 202002L
#include <bit>
#endif
namespace atcoder {
namespace internal {
#if __cplusplus >= 202002L
using std::bit_ceil;
#else
// @return same with std::bit::bit_ceil
unsigned int bit_ceil(unsigned int n) {
unsigned int x = 1;
while (x < (unsigned int)(n)) x *= 2;
return x;
}
#endif
// @param n `1 <= n`
// @return same with std::bit::countr_zero
int countr_zero(unsigned int n) {
#ifdef _MSC_VER
unsigned long index;
_BitScanForward(&index, n);
return index;
#else
return __builtin_ctz(n);
#endif
}
// @param n `1 <= n`
// @return same with std::bit::countr_zero
constexpr int countr_zero_constexpr(unsigned int n) {
int x = 0;
while (!(n & (1 << x))) x++;
return x;
}
} // namespace internal
} // namespace atcoder
namespace atcoder {
#if __cplusplus >= 201703L
template <class S, auto op, auto e> struct segtree {
static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>,
"op must work as S(S, S)");
static_assert(std::is_convertible_v<decltype(e), std::function<S()>>,
"e must work as S()");
#else
template <class S, S (*op)(S, S), S (*e)()> struct segtree {
#endif
public:
segtree() : segtree(0) {}
explicit segtree(int n) : segtree(std::vector<S>(n, e())) {}
explicit segtree(const std::vector<S>& v) : _n(int(v.size())) {
size = (int)internal::bit_ceil((unsigned int)(_n));
log = internal::countr_zero((unsigned int)size);
d = std::vector<S>(2 * size, e());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
S get(int p) const {
assert(0 <= p && p < _n);
return d[p + size];
}
S prod(int l, int r) const {
assert(0 <= l && l <= r && r <= _n);
S sml = e(), smr = e();
l += size;
r += size;
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_prod() const { return d[1]; }
template <bool (*f)(S)> int max_right(int l) const {
return max_right(l, [](S x) { return f(x); });
}
template <class F> int max_right(int l, F f) const {
assert(0 <= l && l <= _n);
assert(f(e()));
if (l == _n) return _n;
l += size;
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!f(op(sm, d[l]))) {
while (l < size) {
l = (2 * l);
if (f(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <bool (*f)(S)> int min_left(int r) const {
return min_left(r, [](S x) { return f(x); });
}
template <class F> int min_left(int r, F f) const {
assert(0 <= r && r <= _n);
assert(f(e()));
if (r == 0) return 0;
r += size;
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!f(op(d[r], sm))) {
while (r < size) {
r = (2 * r + 1);
if (f(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int _n, size, log;
std::vector<S> d;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};
} // namespace atcoder
using F = pair<ll, int>;
F op(F l, F r){
return min(l, r);
}
F e(){
return {ILL, -1};
}
void solve();
// POP'N ROLL MUSIC / TOMOO
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
rep(i, 0, t) solve();
}
void solve(){
int N, M, tm;
cin >> N >> M >> tm;
vector<pair<ll, int>> p(N + M);
rep(i, 0, N + M){
cin >> p[i].first;
p[i].second = (i < N ? 0 : 1);
}
So(p);
vector<int> to(N + M + 1, -1);
vector<ll> base(N + M + 1);
{
ll sum = 0;
vector<F> X((N + M) * 2 + 1, e());
int ind = N + M;
rep(i, 0, N + M + 1){
if (X[ind].second != -1){
base[i] = base[X[ind].second] + abs(sum - X[ind].first);
}
X[ind] = {sum, i};
if (i != N + M){
ind += (1 - p[i].second * 2);
sum += (1 - p[i].second * 2) * p[i].first;
}
}
}
UF T(N + M + 1);
vector<F> seg_base(N + M, e());
rep(i, 0, N + M - 1){
if (p[i].second == p[i + 1].second) continue;
seg_base[i] = {base[i + 2] - base[i], i};
}
atcoder::segtree<F, op, e> seg(seg_base);
ll ans = 0;
// vec_out(base);
// for (auto [a, b] : p) cout << a << " " << b << "\n";
rep(i, 0, tm){
// if (i) cout << " ";
auto tmp = seg.all_prod();
ans += tmp.first;
// cout << ans;
int l = tmp.second, r = T.root(tmp.second + 1);
// cout << tmp.first << " " << tmp.second << " " << l << " " << r << endl;
seg.set(l, e());
seg.set(r, e());
T.unite(l + 1, l);
T.unite(r + 1, r);
int L = -1, R = tmp.second;
while (R - L > 1){
int M = (L + R) / 2;
// cout << M << " " << T.root(M) << "\n";
if (T.root(M) < tmp.second) L = M;
else R = M;
}
if (L != -1){
R = T.root(L + 1);
// cout << "# " << L << " " << R << endl;
if (R != N * 2 && p[R].second != p[L].second) seg.set(L, {base[R + 1] - base[L] + base[L + 1] - base[R], L});
else seg.set(L, e());
}
}
cout << ans << "\n";
}