Submission #753277

#	Time	Username	Problem	Language	Result	Execution time	Memory
753277		boyliguanhan	Tug of War (BOI15_tug)	C++17	18 / 100	25 ms	340 KiB

tug

#include<bits/stdc++.h>
using namespace std;
int pos[20][2], s[20];
bool check(int n, int k, int p) {
    if(__builtin_popcount(p)!=n/2) return 0;
    bool used[n/2][2];
    memset(used, 0, sizeof used);
    int x=0,y=0;
    for(int i = 0; i < n; i++) {
        bool b = p&1<<i;
        used[pos[i][b]-1][b]=1;
        if(b)x+=s[i];
        else y+=s[i];
    }
    for(int i = 0; i < n/2; i++)
        if(!used[i][0]||!used[i][1])
            return 0;
    return abs(x-y) <= k;
}
int main() {
    int n, k;
    cin >> n >> k;
    n*=2;
    for(int i = 0; i < n; i++) {
        cin >> pos[i][0] >> pos[i][1] >> s[i];
    }
    for(int j = (1 << n/2)-1; j < 1 << n; j++) {
        if(j==201) {
            cout << "";
        }
        if(check(n,k,j)) cout << "YES\n", exit(0);
    }
    cout << "NO\n";
}

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