제출 #677204

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
677204		ajab_01	Tug of War (BOI15_tug)	C++17	18 / 100	787 ms	800 KiB

tug

#include<bits/stdc++.h>
using namespace std;

const int N = 3e4 + 4;
int l[N] , r[N] , p[N] , n , k;
bool ch;

bool check(int mask){
	bool vis[N];
	memset(vis , 0 , sizeof(vis));
	int sum1 = 0 , sum2 = 0;
	for(int i = 0 ; i < 2 * n ; i++){
		if(mask & (1 << i)){
			if(vis[r[i]])
				return 0;
			vis[r[i]] = 1;
			sum1 += p[i];
		}
		else{
			if(vis[l[i]])
				return 0;
			vis[l[i]] = 1;
			sum2 += p[i];
		}
	}

	return abs(sum1 - sum2) <= k;
}

int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> k;
	for(int i = 0 ; i < 2 * n ; i++){
		cin >> l[i] >> r[i] >> p[i];
		r[i] += n;
	}

	for(int mask = 0 ; mask < (1 << 2 * n) ; mask++)
		if(check(mask))
			ch = 1;

	if(ch)
		cout << "YES" << '\n';
	else
		cout << "NO" << '\n';
	return 0;
}

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