#670482 (C++14) No.1590 Random Shopping

• 問題: No.1590 Random Shopping
• ユーザー: e869120
• 提出日時: 2021-06-27 00:51:30
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: RE
• 実行時間: -
• コード長: 707 bytes
• コンパイル時間: 787 ms
• コンパイル使用メモリ: 78,200 KB
• 実行使用メモリ: 4,500 KB
• 最終ジャッジ日時: 2023-09-14 04:54:17
• 合計ジャッジ時間: 4,903 ms
• ジャッジサーバーID （参考情報）: judge12 / judge14

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 4,376 KB
testcase_01	AC	1 ms; 4,380 KB
testcase_02	AC	1 ms; 4,384 KB
testcase_03	AC	2 ms; 4,376 KB
testcase_04	AC	1 ms; 4,376 KB
testcase_05	AC	2 ms; 4,376 KB
testcase_06	AC	2 ms; 4,376 KB
testcase_07	AC	948 ms; 4,380 KB
testcase_08	RE	-
testcase_09	RE	-
testcase_10	RE	-
testcase_11	RE	-
testcase_12	RE	-
testcase_13	RE	-
testcase_14	RE	-
testcase_15	RE	-
testcase_16	RE	-
testcase_17	RE	-
testcase_18	AC	2 ms; 4,380 KB
testcase_19	RE	-
testcase_20	AC	1 ms; 4,376 KB
testcase_21	RE	-
testcase_22	AC	1 ms; 4,376 KB
testcase_23	RE	-
testcase_24	RE	-
testcase_25	AC	1 ms; 4,376 KB
testcase_26	AC	1 ms; 4,376 KB
testcase_27	AC	1 ms; 4,380 KB

ソースコード

#include <iostream>
#include <vector>
#include <set>
#include <cassert>
#include <algorithm>
using namespace std;

int N, A[5009], R[5009];

int main() {
	// Step #1. Input
	cin >> N;
	for (int i = 0; i < N; i++) cin >> A[i];
	for (int i = 0; i < N; i++) cin >> R[i];
	assert(N <= 20);

	// Step #2. Brute Force
	double Answer = 0.0, Cnts = 0.0;
	for (int i = 0; i < (1 << N); i++) {
		vector<int> S; double E = 0;
		for (int j = 0; j < N; j++) {
			S.push_back(A[j]);
			sort(S.begin(), S.end());
			reverse(S.begin(), S.end());
			if ((i & (1 << j)) != 0) {
				E += 1.0 * S[S.size() - 1] * R[j];
				S.pop_back();
			}
		}
		Answer += E;
		Cnts += 1.0;
	}
	printf("%.12lf\n", Answer / Cnts);
	return 0;
}