제출 #1174254

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1174254		madamadam3	Tug of War (BOI15_tug)	C++20	18 / 100	78 ms	584 KiB

tug

#include <bits/stdc++.h>

using namespace std;

/*
    SAPO 2025 TC4 Day 1 - Seesaw
    copied from BOI 2015 - Tug of War

    18/100 pt solution here
*/

int main() {
    cin.tie(0)->sync_with_stdio(0);
    
    int n, k; cin >> n >> k;
    vector<int> l(2*n), r(2*n), m(2*n);

    for (int i = 0; i < 2*n; i++) {
        cin >> l[i] >> r[i] >> m[i];
        l[i]--; r[i]--;
    }

    for (int i = 0; i < (1 << (2 * n)); i++) {
        vector<bool> used(2 * n, false);
        int tl = 0;

        bool valid = true;
        for (int bit = 0; bit < 2 * n; bit++) {
            bool has_left = i & (1 << bit);
            int seat = has_left ? l[bit] : n + r[bit];

            if (!used[seat]) used[seat] = true;
            else {valid = false; break;}

            if (has_left) tl += m[bit];
            else tl -= m[bit];
        }
        if (!valid) continue;

        if (abs(tl) <= k) {
            cout << "YES";
            return 0;
        }
    }

    cout << "NO";
    return 0;
}

• Subtask 1: 18 / 18
• Subtask 2: 0 / 30
• Subtask 3: 0 / 23
• Subtask 4: 0 / 29