結果

問題 No.3634 Made to order
コンテスト
ユーザー achapi
提出日時 2026-08-21 22:38:48
言語 C++17
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 1,030 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,213 ms
コンパイル使用メモリ 223,064 KB
実行使用メモリ 318,976 KB
最終ジャッジ日時 2026-08-21 22:38:56
合計ジャッジ時間 5,984 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
サブタスク $1$ 20 % AC * 8
サブタスク $2$ 10 % AC * 18 WA * 3
サブタスク $3$ 70 % AC * 18 WA * 8
合計 3 * 20% = 60 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
int main(){
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	int N, D;
	cin >> N >> D;
	vector<int> A(N), B(N), C(N);
	for (int i = 0; i < N; i++){
		cin >> A[i] >> B[i] >> C[i];
	}
	const short inf = 10000;
	D = min(D, 1500);
	vector dp(1 << N, vector(N, vector(D, inf)));
	for (int i = 0; i < N; i++){
		dp[1 << i][i][A[i]] = A[i] + B[i];
	}
	for (int i = 0; i < (1 << N); i++){
		for (int j = 0; j < N; j++){
			for (int k = 0; k < D; k++){
				if (dp[i][j][k] != inf){
					for (int l = 0; l < N; l++){
						if ((i >> l & 1) == 0 and k + max(B[j], A[l]) < D){
							dp[i | (1 << l)][l][k + max(B[j], A[l])] = min<short>(dp[i | (1 << l)][l][k + max(B[j], A[l])], max(dp[i][j][k] + C[j], k + max(B[j], A[l]) + B[l]));
						}
					}
				}
			}
		}
	}
	bool ok = false;
	for (int i = 0; i < N; i++){
		for (int j = 0; j < D; j++){
			if (dp[(1 << N) - 1][i][j] + C[i] <= D){
				ok = true;
			}
		}
	}
	if (ok){
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}
}
0