接着剤の精進日記

競プロでの精進や研究に関係したことを書いていきます。

AtCoder Beginner Contest 174(ABC174)

atcoder.jp

A - Air Conditioner

 X \geq 30なら"Yes"、そうでなければ"No"
提出コード

void solve(){
    int X;
    cin >> X;
    if(X >= 30) cout << "Yes" << endl;
    else cout << "No" << endl;
}

B - Distance

ルートを外してあげてx^2 + y^2 \leq D ^2ならカウントしていく
提出コード

void solve(){
    ll N, D;
    cin >> N >> D;
    int cnt = 0;
    REP(i,N){
        ll x, y;
        cin >> x >> y;
        x *= x, y *= y;
        if(x + y <= D * D) cnt++;
    }
    cout << cnt << endl;
}

C - Repsept

難しい
Kが偶数のときは絶対作れないのでそれ以外を考えてみる
愚直に求めていくことを考えると、割り算の要領で先頭からmodを取っていく
その時、mod K が0になればその桁を出力する
コンテスト中は厳密な証明出来なかったのでK桁目まで見れば十分そうだなーで投げちゃった
解説にちゃんと証明が載っていたので読みます
提出コード

void solve(){
    int K;
    cin >> K;

    int cur = 0;
    REP(i,K+1){
        cur = cur * 10 + 7;
        cur %= K;
        if(cur == 0){
            cout << i + 1 << endl;
            return;
        }
    }
    cout << -1 << endl;
}

D - Alter Altar

これも結構考えちゃったんだけど茶色difficultyらしくてびっくり
最終的な状態を考えると、
RR...RWW...W
WW...W
RR...R
のどれかになっていればいい
これを達成するには一番左にあるWと一番右にあるRをswapすることを繰り返していけばいい
提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> R, W;
    REP(i,N){
        char c;
        cin >> c;
        if(c == 'R') R.emplace_back(i);
        else W.emplace_back(i);
    }
    if(size(R) == 0 or size(W) == 0){
        cout << 0 << endl;
        return;
    }
    sort(R.rbegin(), R.rend());
    int r = 0;
    int ans = 0;
    REP(i, size(W)){
        if(W[i] < R[r]){
            ans++;
            if(size(R) > r) r++;
        }
        if(size(R) == r) break;
    }
    cout << ans << endl;
}

E - Logs

最大値の最小化はにぶたん(素振り)
操作を行った後の丸太の長さの最大値をxにできるかどうか、という判定問題を考える
長さA_iの丸太を長さxで分割していくことを考えると \lceil \frac{A_i}{x} \rceil - 1回切る必要がある
そのため、この合計回数がK回以内なら達成でき、そうでないなら達成できない
あとは、このxについて二分探索をするとこの問題を解くことができる
提出コード

void solve(){
    ll N, K, ma = 0;
    cin >> N >> K;
    vector<ll> A(N);
    REP(i,N){
        cin >> A[i];
        chmax(ma, A[i]);
    }

    auto check = [&](ll x) -> ll{
        if(x == 0) return LINF;
        ll cnt = 0;
        REP(i,N) cnt += (A[i] + x - 1)/ x - 1;
        return cnt;
    };
    ll l = 0, r = ma+1;
    while(r - l > 1){
        ll m = (r + l) >> 1;
        if(check(m) <= K) r = m;
        else l = m;
    }
    cout << l+1 << endl;
}

F - Range Set Query

以下の記事を読んだ記憶があったので「区間 種類数」みたいにググるとHitする
hama-du-competitive.hatenablog.com その後に類題でググってるとけんちょんさんの記事があったのでそれをペタりました
drken1215.hatenablog.com 典型らしいのでちゃんと中身理解しておきたいね
提出コード

void solve(){
    int N, Q;
    cin >> N >> Q;
    vector<int> a(N);
    REP(i,N) cin >> a[i];
    vector<int> lefts(Q), rights(Q), ids(Q);
    REP(i,Q){
        cin >> lefts[i] >> rights[i];
        --lefts[i];
        ids[i] = i;
    }
    sort(ids.begin(), ids.end(), [&](int i, int j) {
            return rights[i] < rights[j];});

    BIT<int> bit(N+10);
    vector<int> prev(505050, -1);
    vector<int> res(Q);
    int r = 0;
    for (auto i : ids) {
        for (; r < rights[i]; ++r) {
            bit.add(prev[a[r]]+2, r+2, 1);
            prev[a[r]] = r;
        }
        int tmp = bit.sum(lefts[i]+1, lefts[i]+2);
        res[i] = max(res[i], tmp);
    }
    for (int i = 0; i < Q; ++i) cout << res[i] << endl;
}

M-SOLUTIONS プロコンオープン 2020

atcoder.jp

A - Kyu in AtCoder

if文全部書く
楽できそうな気もしたけどこっちのほうが早そうだった
提出コード

void solve(){
    int X;
    cin >> X;
    int ans = 0;
    if(X <= 599) ans = 8;
    else if(X <= 799) ans = 7;
    else if(X <= 999) ans = 6;
    else if(X <= 1199) ans = 5;
    else if(X <= 1399) ans = 4;
    else if(X <= 1599) ans = 3;
    else if(X <= 1799) ans = 2;
    else if(X <= 1999) ans = 1;
    cout << ans << endl;
}

B - Magic 2

ちょっとこどふぉっぽい気がした
A \lt B \lt Cとなるまでに必要な操作回数をシミュレートしてそれがK回以内でできるか判定すればいい
提出コード

void solve(){
    int A, B, C, K;
    cin >> A >> B >> C >> K;
    int cnt = 0;
    while(A >= B){
        B *= 2;
        cnt++;
    }
    while(B >= C){
        C *= 2;
        cnt++;
    }
    if(cnt <= K) cout << "Yes" << endl;
    else cout << "No" << endl;
}

C - Marks

これ累積和でもいいの面白いね
i学期とi-1学期との差異はA_iA_{i-K}なのでこの大小比較を行えばいい
提出コード

void solve(){
    int N, K;
    cin >> N >> K;
    vector<int> A(N);
    REP(i,N) cin >> A[i];
    for(int i=K;i<N;i++){
        if(A[i-K] >= A[i]) cout << "No" << endl;
        else cout << "Yes" << endl;
    }
}

D - Road to Millionaire

未来がわかっても最大化出来ないので株やりません(?)
まず、各日で株を持っていたら同額で買い直せるのでそれを全て売ってしまっていい
今がi日目だとすると、A_i \lt A_{i+1}ならば株を買えばその分必ず得をする
逆にA_i \geq A_{i+1}のときは買っても損をするだけになる
そのため、各日の最初に持っている株を全部売り、A_i \lt A_{i+1}の時買えるだけ買えばいい
提出コード

void solve(){
    int N;
    cin >> N;
    vector<ll> A(N);
    REP(i,N) cin >> A[i];

    ll cur = 1000;
    ll kabu = 0;
    REP(i,N){
        cur += kabu * A[i];
        kabu = 0;
        if(i == N-1) break;
        if(A[i] < A[i+1]){
            kabu += cur / A[i];
            cur -= cur / A[i] * A[i];
        }
    }

    cout << cur << endl;
}

E - M's Solution

ぱっと見全探索できそうな制約なのでまず全探索を考えてみる
サンプルを睨むと各集落のx座標もしくはy座標を通るような辺のみを考えれば良さそう
これはある鉄道Lを考えると、Lを選ぶ集落だけを抜き出すと中央値と同じ議論ができるため、集落のうちどこかを通る(これ頭いい)
これは\mathcal{O}(3^N)で出来そう
実際には毎回コスト計算をすると\mathcal{O}(3^N \times N ^ 2)かかりTLEになる
コンテスト中はここから計算量削れなくて終わったけど、前計算することで計算量を落とせる
x軸方向とy軸方向に分けてコストを前計算する
それぞれについて、2 ^ N通り前計算をすると
前計算に\mathcal{O}(2 ^ N \times N ^ 2)、全探索部分に\mathcal{O}(3 ^ N \times N)でこの問題を解くことができる
全探索部分は再帰が楽だと思う(ループで部分集合列挙のほうが良かったりするのかな)
提出コード

void solve(){
    int N;
    cin >> N;
    vector<ll> X(N), Y(N), P(N);
    REP(i,N) cin >> X[i] >> Y[i] >> P[i];
    vector<vector<ll>> costX(1<<N, vector<ll>(N, LINF));
    auto costY = costX;
    REP(i,1<<N){
        REP(j,N){
            costX[i][j] = abs(X[j]);
            costY[i][j] = abs(Y[j]);
            REP(k,N) if(i >> k & 1){
                chmin(costX[i][j], abs(X[j] - X[k]));
                chmin(costY[i][j], abs(Y[j] - Y[k]));
            }
        }
    }

    vector<ll> ans(N+1, LINF);
    auto dfs = [&](auto && self, vector<int> &state) -> void{
        if(size(state) == N){
            ll x = 0, y = 0;
            int cnt = 0;
            REP(i,N){
                if(state[i] == 0) continue;
                cnt++;
                if(state[i] == 1) x |= (1LL << i);
                else if(state[i] == 2) y |= (1LL << i);
            }

            ll sum = 0;
            REP(i,N){
                sum += P[i] * min(costX[x][i], costY[y][i]);
            }
            chmin(ans[cnt], sum);
        }
        else{
            REP(i,3){
                state.emplace_back(i);
                self(self, state);
                state.pop_back();
            }
        }
    };

    vector<int> state;
    dfs(dfs, state);
    REP(i,N+1) cout << ans[i] << endl;
}

エイシング プログラミング コンテスト 2020

atcoder.jp

A - Number of Multiples

f(R) - f(L-1)を求めるやつ
制約が小さいので全探索でいい
提出コード

void solve(){
    int L, R, D;
    cin >> L >> R >> D;
    int ans = 0;
    for(int i=L;i<=R;i++) if(i % D == 0) ans++;
    cout << ans << endl;
}

B - An Odd Problem

ia_iがどちらも奇数のものをカウントする
提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> a(N+1);
    int ans = 0;
    for(int i=1;i<=N;i++){
        cin >> a[i];
        if((i & 1) && (a[i] & 1)) ans++;
    }
    cout << ans << endl;
}

C - XYZ Triplets

x^2を考えるとx = 100のときx^2 = 10^4になるので
1 \leq x, y, z \leq 100程度で全探索すればいい
提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> cnt(N+10);
    for(ll i=1;i<=300;i++){
        for(ll j=1;j<=300;j++){
            for(ll k=1;k<=300;k++){
                ll x = i*i + j*j + k*k + i*j + j*k + k*i;
                if(x > N) continue;
                cnt[x]++;
            }
        }
    }
    for(int i=1;i<=N;i++) cout << cnt[i] << endl;
}

D - Anything Goes to Zero

最初の1回目の操作を考えると最大でも2 \times 10^5で割った余りを求めるので、一回目の操作の値を求めることが出来れば、後は愚直に操作が出来る
1回の操作でpopcount(X)の値はpopcount(X) \pm 1の2通りしか無いのでX mod (popcount(X) \pm 1)を前計算しておく
そうすると、一回目の操作後の値は、そのbitを反転させたときの差分と、前計算した2通りのどちらかのmodを使って求めることが出来る
二回目以降は愚直に操作をすればいい
ただし、操作を行ったときに0になる時の場合分けが必要
提出コード

void solve(){
    int N;
    string S;
    cin >> N >> S;
    int cnt = 0;
    reverse(S.begin(), S.end());
    REP(i,N) if(S[i] == '1') cnt++;
    ll x1 = 0, x2 = 0;
    REP(i,N){
        if(S[i] == '1'){
            if(cnt > 1){
                x1 += mod_pow(2, i, cnt-1);
                x1 %= (cnt - 1);
            }
            x2 += mod_pow(2, i, cnt+1);
            x2 %= (cnt + 1);
        }
    }
    vector<int> ans(N);
    REP(i,N){
        if(S[i] == '1'){
            if(cnt == 1){
                ans[i] = 0;
                continue;
            }
            ll tmp = x1 - mod_pow(2, i, cnt - 1) + (cnt - 1);
            tmp %= (cnt - 1);
            ans[i]++;
            while(tmp > 0){
                ans[i]++;
                tmp %= __builtin_popcount(tmp);
            }
        }
        else{
            ll tmp = x2 + mod_pow(2, i, cnt+1);
            tmp %= (cnt + 1);
            ans[i]++;
            while(tmp > 0){
                ans[i]++;
                tmp %= __builtin_popcount(tmp);
            }
        }
    }
    reverse(ans.begin(), ans.end());
    REP(i,N) cout << ans[i] << endl;
}

E - Camel Train

 L_i \geq R_iL_i \lt R_iに分けて考える
前者は出来るだけ左側に寄せて、後者は出来るだけ右側に寄せた方がお得
後者より右側に前者が存在する場合、その部分を入れ替えても損をすることは無いので、それぞれ独立に考えても良いことがわかる
前者を考えると、どの位置においても最低R_iは得られる
ラクiK_i番目以内にいる時、L_i - R_iが追加で得られる
そうすると、制約がきついほうから考えると左側から順にi = K_jとなるようなラクダのL_j - R_jをpriority_queueに入れていき、size(pq) > iなら小さい方から取り除いていき、残ったものの総和を加算する
後者の場合も同様に右側から順に処理をしていき、最後に残ったものの総和を加算する
提出コード

void solve(){
    int N;
    cin >> N;
    vector<vector<ll>> vp(N+10), vm(N+10);
    ll ans = 0;
    int cnt = 0;
    REP(i,N){
        int K, L, R;
        cin >> K >> L >> R;
        if(L >= R){
            vp[K].emplace_back(L - R);
            ans += R;
            cnt++;
        }
        else{
            ans += L;
            vm[K].emplace_back(R - L);
        }
    }

    priority_queue<ll, vector<ll>, greater<ll>> pq, pq2;
    for(int i=1;i<=N;i++){
        for(auto x : vp[i]) pq.emplace(x);
        while(size(pq) > i) pq.pop();
    }
    while(!pq.empty()) ans += pq.top(), pq.pop();

    for(int i=N;i>=1;i--){
        for(auto x : vm[i]) pq2.emplace(x);
        while(size(pq2) > N - i) pq2.pop();
    }
    while(!pq2.empty()) ans += pq2.top(), pq2.pop();
    cout << ans << endl;
}

AtCoder Beginner Contest 173(ABC173)

atcoder.jp

A - Payment

Nを超える最小の1000の倍数からNを引く
Nが小さいからループでもいい
提出コード

void solve(){
    int N;
    cin >> N;
    int cnt = (N + 999) / 1000;
    cout << cnt * 1000 - N << endl;
}

B - Judge Status Summary

注意力?
それぞれでカウントして出力形式に気をつける
提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> cnt(5);
    REP(i,N){
        string s;
        cin >> s;
        if(s == "AC") cnt[0]++;
        if(s == "WA") cnt[1]++;
        if(s == "TLE") cnt[2]++;
        if(s == "RE") cnt[3]++;
    }
    cout << "AC x " << cnt[0] << endl;
    cout << "WA x " << cnt[1] << endl;
    cout << "TLE x " << cnt[2] << endl;
    cout << "RE x " << cnt[3] << endl;
}

C - H and V

制約が小さいのでどこを選ぶかをbit全探索する
bit全探索出来るならこっちのほうが簡潔な気がするけど再帰で書いた人もいるっぽい
提出コード(bit全探索)

void solve(){
    int H, W, K;
    cin >> H >> W >> K;
    vector<string> fi(H);
    REP(i,H) cin >> fi[i];
    int ans = 0;
    REP(h, 1<<H) REP(w,1<<W){
        vector<string> tmp = fi;
        REP(i,H) if(h >> i & 1){
            REP(k,W) tmp[i][k] = '?';
        }
        REP(i,W) if(w >> i & 1){
            REP(k,H) tmp[k][i] = '?';
        }
        int cnt = 0;
        REP(i,H) REP(j,W){
            if(tmp[i][j] == '#') cnt++;
        }
        if(cnt == K) ans++;
    }
    cout << ans << endl;
}

提出コード(再帰)

void solve(){
    int H, W, K;
    cin >> H >> W >> K;
    vector<string> fi(H);
    REP(i,H) cin >> fi[i];
    int ans = 0;
    auto dfs = [&](auto && self, vector<int> &v) ->void{
        if(size(v) == H + W){
            auto tmp = fi;
            REP(i,H) if(v[i] == 1){
                REP(j,W) tmp[i][j] = '?';
            }
            REP(j,W) if(v[H+j] == 1){
                REP(i,H) tmp[i][j] = '?';
            }
            int cnt = 0;
            REP(i,H) REP(j,W){
                if(tmp[i][j] == '#') cnt++;
            }
            if(cnt == K) ans++;
        }
        else{
            REP(i,2){
                v.push_back(i);
                self(self, v);
                v.pop_back();
            }
        }
    };
    vector<int> v;
    dfs(dfs, v);
    cout << ans << endl;
}

D - Chat in a Circle

これ難しくない?
最初に到達人以外を考える
2人目は最初に来た人の値になるので最初の人は高いほうが良い
2人目以降は自分が割り込んだ位置の時計回りと反時計回り方向に自分の値の区間が出来る
そのため、降順ソートをし、区間の大きい値を貪欲にとっていく
そうすると降順ソートした後、数列の先頭から 1, 2, 2, 2, ..., の回数だけ値を加算できる
提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> A(N);
    REP(i,N) cin >> A[i];
    sort(A.rbegin(), A.rend());
    priority_queue<int> pq;
    ll ans = 0;
    REP(i,N){
        if(i == 0){
            pq.push(A[i]);
            continue;
        }
        ans += pq.top(); pq.pop();
        pq.push(A[i]);
        pq.push(A[i]);
    }
    cout << ans << endl;
}

E - Multiplication 4

頭壊れる
N = Kときは自明
すべての値が負なら、絶対値の小さい順に掛けていく
それ以外の場合は必ず非負に出来る
絶対値の降順にソートをし、大きい順にK個取る
その時点で値が非負ならそれが答え
負になった時、選んだものの中から負のものを1個取って、選んでないものの中から1個非負を選ぶ
もしくは、正のものを1個取って、負を1個取る
選んだものの中からは出来るだけ小さいものを取りたい、また、選んでないものの中からは出来るだけ大きいものを取りたいのでこれは一意に定まる
この2つのうち、積が大きくなる方を選べばいいが、片方しか選べないときがあるので注意する
提出コード

void solve(){
    int N, K;
    cin >> N >> K;
    vector<ll> A(N);
    int plus = 0, minus = 0;

    REP(i,N){
        cin >> A[i];
        if(A[i] >= 0) plus++;
        else  minus++;
    }
    mint ans = 1;
    if(N == K){
        REP(i,N) ans *= A[i];
        cout << ans << endl;
        return;
    }
    if((K & 1) && plus == 0){
        REP(i,N) if(A[i] < 0) A[i] *= -1;
        sort(A.begin(), A.end());
        REP(i,K) ans *= A[i];
        ans = -ans;
        cout << ans << endl;
        return;
    }
    bool flg = false;
    sort(A.begin(), A.end(), [&](int x, int y){return abs(x) > abs(y);});
    ll m = -LINF, p = LINF;

    REP(i,K){
        ans *= A[i];
        if(A[i] < 0){
            flg = 1 - flg;
            chmax(m, A[i]);
        }
        else chmin(p, A[i]);
    }

    if(!flg){
        cout << ans << endl;
        return;
    }

    ll c1 = LINF, c2 = LINF;
    for(int i=K;i<N;i++){
        if(A[i] >= 0 && c1 == LINF){
            c1 = A[i];
        }
        if(A[i] < 0 && c2 == LINF){
            c2 = A[i];
        }
    }

    if((p != LINF && c2 != LINF) && (m == -LINF || c1 == LINF)) cout << ans / p * c2 << endl;
    else if((p == LINF || c2 == LINF) && (m != -LINF && c1 != LINF)) cout << ans / m * c1 << endl;
    else if(abs(c1 * p) <= abs(c2 * m)) cout << ans / p * c2 << endl;
    else cout << ans / m * c1 << endl;
}

F - Intervals on Tree

 \sum (連結成分数)を求めたい
これを愚直に求めると\sum^{N}_{L=1} \sum^{N}_{R=L} f(L,R)となり\mathcal{O}(N^2)かかってしまう
ここで、木の誘導グラフを考えるとそれらはすべて森となる
森の場合の連結成分数は(頂点数) - (辺の数)で求めることが出来る
よって
\sum (連結成分数) = \sum (頂点数) - (辺の数)
 = \sum (頂点数) - \sum (辺の数)として求めることが出来る
頂点数は、長さi区間が何個出来るかで \sum^{N}_{i=1} i \times (N - i + 1)で求められる
辺の数は、ある辺が何回寄与するかを考える
 u \lt vとするとuvが含まれる区間というのは 1 \leq l \leq uかつ v \leq r \leq Nを満たす区間なので
 u \times (N - v + 1)が各辺が寄与する回数となり、その総和を求めた後、辺の数からこれを引いてあげればいい
提出コード

void solve(){
    ll N;
    cin >> N;
    ll vertices = 0, edges = 0;
    for(int i=1;i<=N;i++){
        vertices += i * (N - i + 1);
    }
    REP(i,N-1){
        ll u, v;
        cin >> u >> v;
        if(u > v) swap(u, v);
        edges += u * (N - v + 1);
    }
    cout << vertices - edges << endl;
}

Codeforces Round #653 (Div. 3)

codeforces.com

A. Required Remainder

kはxの倍数にyだけ足したものと考えていいので
nを超えない範囲のxの倍数を求めてからyを足す
提出コード

void solve(){
    ll x, y, n;
    cin >> x >> y >> n;
    ll k = n / x * x;
    if(k + y <= n) cout << k + y << endl;
    else cout << k - x + y << endl;
}

B. Multiply by 2, divide by 6

まず3で割り切れないときは答えは-1になる
また、2と3以外の素因数が含まれる場合も-1になる
nを3で割れる回数をthree, 2で割れる回数をtwoとする
操作は素因数2を増やすか6で割るかなので two \gt threeなら不可能
それ以外の場合min(two, three) + 2 * (three - min(two, three))となる
提出コード

void solve(){
    int n;
    cin >> n;
    if(n == 1){
        cout << 0 << endl;
        return;
    }
    if(n % 3){
        cout << -1 << endl;
        return;
    }
    int tmp = n;
    int three = 0;
    while(tmp % 3 == 0) three++, tmp /= 3;
    int two = 0;
    while(tmp % 2 == 0) two++, tmp /= 2;
    if(tmp > 1){
        cout << -1 << endl;
        return;
    }
    if(two > three){
        cout << -1 << endl;
        return;
    }
    int ans = min(two, three);
    three -= ans;
    ans += 2 * three;
    cout << ans << endl;
}

C. Move Brackets

操作をする前に'(' と ')'が並んでいるものは取ってしまっていい
これはstackなどでシミュレートする
次に残ったものに対し操作を行い'('と')'のペアを作る
この時、1回の操作でペアを作ることが出来るので
シミュレートして残った文字列の長さを2で割ったものが答え
提出コード

void solve(){
    int n;
    string s;
    cin >> n >> s;
    vector<char> st;
    REP(i,n){
        if(st.empty()) st.push_back(s[i]);
        else{
            if(st.back() == '(' && s[i] == ')') st.pop_back();
            else st.push_back(s[i]);
        }
    }
    cout << st.size() / 2 << endl;
}

D. Zero Remainder Array

操作を行い、最終的にxが幾つになるか考える
A_iをmod k で考えると同じ余りの組はその個数分の周期が必要になる
そのため、各mod k の値ごとにxが最大で幾つになるかのmaxを求めてあげればいい
提出コード

void solve(){
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    map<ll, ll> mp;
    REP(i,n){
        cin >> a[i];
        a[i] %= k;
        mp[a[i]]++;
    }
    ll ans = 0;
    for(auto [x, y] : mp){
        if(x == 0) continue;
        // cout << k - x << " " << x << " " << y << endl;
        chmax(ans, k*(y-1) + k-x + 1);
    }
    cout << ans << endl;
}

E1. Reading Books (easy version)

この間のABC-Cと同じような感じ
AliceとBobが本をi個共有する時、残りのk-i個はtの小さい順に読むのが最適となる
AliceとBob、また共有する本をそれぞれ配列に入れ、昇順にソートした後
AliceとBobの配列の累積和を取っておき、共有する本の数を全探索すればいい
提出コード

void solve(){
    int n, k;
    cin >> n >> k;
    vector<int> alice, bob, both;
    REP(i,n){
        int t, a, b;
        cin >> t >> a >> b;
        if(a & b) both.emplace_back(t);
        else if(a) alice.emplace_back(t);
        else if(b) bob.emplace_back(t);
    }
    sort(alice.begin(), alice.end());
    sort(bob.begin(), bob.end());
    sort(both.begin(), both.end());

    int a = alice.size(), b = bob.size(), c = both.size();
    vector<ll> cum_a(a+1), cum_b(b+1);
    for(int i=0;i<a;i++){
        cum_a[i+1] = cum_a[i] + alice[i];
    }
    for(int i=0;i<b;i++){
        cum_b[i+1] = cum_b[i] + bob[i];
    }
    ll ans = LINF;
    ll sum = 0;
    REP(i,min(c, k)){
        sum += both[i];
        int rest = k - i - 1;
        if(rest > b || rest > a) continue;
        chmin(ans, sum + cum_a[rest] + cum_b[rest]);
    }
    if(k <= a && k <= b) chmin(ans, cum_a[k] + cum_b[k]);
    if(ans == LINF) ans = -1;
    cout << ans << endl;
}