oj.uz

답안 #897377

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
897377 2024-01-03T02:54:33 Z Wobert Palembang Bridges (APIO15_bridge) C++17
22 / 100
 55 ms 11220 KB 
#include "bits/stdc++.h"
#ifdef LOCAL
#include "dbg.h"
#else
#define dbg(...) 0
#endif

#define fox(i, n) for (int i = 0; i < (n); ++i)
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define rin(i, a, b) for (int i = (a); i <= (b); ++i)
#define rrep(i, a, b) for (int i = (a); i >= (b); --i)
#define fore(x, v) for (auto &&x : v)
#define forp(a, b, v) for (auto &&[a, b] : v)
#define pb push_back
#define eb emplace_back
#define F first
#define S second
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define EL "\n"

using namespace std;

using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vpii = vector<pii>;
using vpll = vector<pll>;
template<class T> using pq = priority_queue<T>;
template<class T> using pqg = priority_queue<T, vector<T>, greater<>>;

template<class T>
int sz(T& container) {
    return (int) container.size();
}
template<class T> bool ckmin(T& a, const T& b) {
    return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) {
    return a < b ? a = b, 1 : 0; }

ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); }
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); }

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//ll urand(int a, int b) { return rng() % (b-a+1) + a; }

//const vector<pii> deltas = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
const int INF = 0x3f3f3f3f;

template<int MOD, int RT> struct mint {
    static const int mod = MOD;
    static constexpr mint rt() { return RT; } // primitive root for FFT
    int v; explicit operator int() const { return v; } // explicit -> don't silently convert to int
    mint():v(0) {}
    mint(ll _v) { v = int((-MOD < _v && _v < MOD) ? _v : _v % MOD);
        if (v < 0) v += MOD; }
    bool operator==(const mint& o) const {
        return v == o.v; }
    friend bool operator!=(const mint& a, const mint& b) {
        return !(a == b); }
    friend bool operator<(const mint& a, const mint& b) {
        return a.v < b.v; }

    mint& operator+=(const mint& o) {
        if ((v += o.v) >= MOD) v -= MOD;
        return *this; }
    mint& operator-=(const mint& o) {
        if ((v -= o.v) < 0) v += MOD;
        return *this; }
    mint& operator*=(const mint& o) {
        v = int((ll)v*o.v%MOD); return *this; }
    mint& operator/=(const mint& o) { return (*this) *= inv(o); }
    friend mint pow(mint a, ll p) {
        mint ans = 1; assert(p >= 0);
        for (; p; p /= 2, a *= a) if (p&1) ans *= a;
        return ans; }
    friend mint inv(const mint& a) { assert(a.v != 0);
        return pow(a,MOD-2); }

    mint operator-() const { return mint(-v); }
    mint& operator++() { return *this += 1; }
    mint& operator--() { return *this -= 1; }
    friend mint operator+(mint a, const mint& b) { return a += b; }
    friend mint operator-(mint a, const mint& b) { return a -= b; }
    friend mint operator*(mint a, const mint& b) { return a *= b; }
    friend mint operator/(mint a, const mint& b) { return a /= b; }

    friend istream& operator>> (istream& is, mint& a) {
        is >> a.v;
        return is;
    }
    friend ostream& operator<< (ostream& os, const mint& a) {
        os << a.v;
        return os;
    }
};

using mi = mint<int(1e9+7), 5>;

struct bridge {
    pq<ll> left; // sz(left) >= sz(right)
    pqg<ll> right;
    ll cost{};
    // median = left.top()

    void adjust(bool l) {
        ll old, dif;
        if (l) {
            if (sz(left) - sz(right) <= 1) return;
            old = left.top(); left.pop();
            dif = left.top() - old;
        } else {
            if (sz(left) >= sz(right)) return;
            old = right.top(); right.pop();
            dif = old - left.top();
            cost -= dif;
        }
        cost += dif * sz(left);
        cost -= dif * sz(right);
        if (l) right.push(old);
        else left.push(old);
    }

    void insert(ll p) {
        if (left.empty()) {
            left.push(p); return;
        }
        cost += abs(p - left.top());
        if (p > left.top()) {
            right.push(p);
            adjust(false);
        } else {
            left.push(p);
            adjust(true);
        }
    }

    void insert(pll p) {
        insert(p.F); insert(p.S);
    }
};


void solve() {
    int k, n; cin >> k >> n;
    ll ans = 0;
    vpll v;
    fox(i, n) {
        char a, b; int x, y; cin >> a >> x >> b >> y;
        if (a == b) ans += abs(x-y);
        else {
            v.eb(minmax(x, y)); ++ans;
        }
    }
    sort(all(v), [](pll a, pll b) {return a.F+a.S < b.F+b.S;});

    n = sz(v);
    vll lcost(n+1), rcost(n+1);
    bridge l, r;
    rin(i, 1, n) {
        l.insert(v[i-1]);
        r.insert(v[n-i]);
        lcost[i] = l.cost;
        rcost[i] = r.cost;
    }
    ll best;
    if (k == 1) {
        best = lcost[n];
    } else {
        best = 1e18;
        rin(i, 0, n)
            ckmin(best, lcost[i] + rcost[n-i]);
    }
    cout << best + ans << EL;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    int t;
//    cin >> t;
//    while (t--)
        solve();
    return 0;
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 476 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 504 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 348 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 23 ms 9080 KB Output is correct
13 Correct 55 ms 10600 KB Output is correct
14 Correct 45 ms 9412 KB Output is correct
15 Correct 28 ms 5972 KB Output is correct
16 Correct 22 ms 10708 KB Output is correct
17 Correct 41 ms 11216 KB Output is correct
18 Correct 25 ms 9928 KB Output is correct
19 Correct 47 ms 11220 KB Output is correct
20 Correct 32 ms 9988 KB Output is correct
21 Correct 44 ms 10948 KB Output is correct

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 1 ms 344 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Incorrect 0 ms 448 KB Output isn't correct
5 Halted 0 ms 0 KB -