Submission #6665447


Source Code Expand

Copy
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
            ∧_∧
      ∧_∧  (´<_` )  Welcome to My Coding Space!
     ( ´_ゝ`) /  ⌒i     @hamayanhamayan
    /   \     | |
    /   / ̄ ̄ ̄ ̄/  |
  __(__ニつ/     _/ .| .|____
     \/____/ (u ⊃
---------------------------------------------------------------------------------------------------*/










int N, M, A[20], B[20];
vector<ll> sanada;
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> M;
	rep(i, 0, N) cin >> A[i];
	rep(i, 0, M) cin >> B[i];

	ll anmichi_tot = 0;
	rep(i, 0, N) anmichi_tot += A[i];
	ll sanada_tot = 0;
	rep(i, 0, M) sanada_tot += B[i];

	rep(msk, 0, 1 << M) {
		ll a = 0, b = 0;
		int acnt = 0, bcnt = 0;
		rep(i, 0, M) {
			if (msk & (1 << i)) a += B[i], acnt++;
			else b += B[i], bcnt++;
		}
		if (0 < acnt and 0 < bcnt and a > b) sanada.push_back(a);
	}
	sort(all(sanada));
	sanada.push_back(infl);

	double ans = 0;
	rep(msk, 0, 1 << N) {
		ll a = 0, b = 0;
		int acnt = 0, bcnt = 0;
		rep(i, 0, N) {
			if (msk & (1 << i)) a += A[i], acnt++;
			else b += A[i], bcnt++;
		}
		if (0 < acnt and 0 < bcnt and a > b) {
			ll lft = sanada_tot - anmichi_tot + a;
			ll rht = a;
			
			auto lft_ite = upper_bound(all(sanada), lft);
			auto rht_ite = lower_bound(all(sanada), rht);

			int aa_cnt = rht_ite - lft_ite;
			int aa_all_cnt = sanada.size() - 1;
			if(0 < aa_cnt) chmax(ans, 1.0 * aa_cnt / aa_all_cnt);
		}
	}
	printf("%.10f\n", ans);
}

Submission Info

Submission Time
Task J - school competition 2
User hamayanhamayan
Language C++14 (GCC 5.4.1)
Score 500
Code Size 2463 Byte
Status
Exec Time 350 ms
Memory 6512 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_1.txt, sample_2.txt
Subtask1 500 / 500 sample_1.txt, sample_2.txt, testcase_01.txt, testcase_02.txt, testcase_03.txt, testcase_04.txt, testcase_05.txt, testcase_06.txt, testcase_07.txt, testcase_08.txt, testcase_09.txt, testcase_10.txt, testcase_11.txt, testcase_12.txt, testcase_13.txt, testcase_14.txt, testcase_15.txt, testcase_16.txt, testcase_17.txt, testcase_18.txt, testcase_19.txt, testcase_20.txt, testcase_21.txt, testcase_22.txt, testcase_23.txt, testcase_24.txt, testcase_25.txt, testcase_26.txt, testcase_27.txt, testcase_28.txt, testcase_29.txt, testcase_30.txt, testcase_31.txt, testcase_32.txt, testcase_33.txt, testcase_34.txt, testcase_35.txt, testcase_36.txt, testcase_37.txt, testcase_38.txt, testcase_39.txt, testcase_40.txt
Case Name Status Exec Time Memory
sample_1.txt 1 ms 256 KB
sample_2.txt 1 ms 256 KB
testcase_01.txt 2 ms 256 KB
testcase_02.txt 3 ms 256 KB
testcase_03.txt 16 ms 640 KB
testcase_04.txt 6 ms 256 KB
testcase_05.txt 12 ms 640 KB
testcase_06.txt 4 ms 512 KB
testcase_07.txt 1 ms 256 KB
testcase_08.txt 1 ms 256 KB
testcase_09.txt 1 ms 256 KB
testcase_10.txt 163 ms 6128 KB
testcase_11.txt 7 ms 640 KB
testcase_12.txt 1 ms 256 KB
testcase_13.txt 4 ms 512 KB
testcase_14.txt 50 ms 2420 KB
testcase_15.txt 1 ms 256 KB
testcase_16.txt 33 ms 256 KB
testcase_17.txt 2 ms 256 KB
testcase_18.txt 4 ms 512 KB
testcase_19.txt 13 ms 256 KB
testcase_20.txt 50 ms 2420 KB
testcase_21.txt 17 ms 256 KB
testcase_22.txt 1 ms 256 KB
testcase_23.txt 14 ms 256 KB
testcase_24.txt 1 ms 256 KB
testcase_25.txt 3 ms 384 KB
testcase_26.txt 4 ms 512 KB
testcase_27.txt 1 ms 256 KB
testcase_28.txt 1 ms 256 KB
testcase_29.txt 13 ms 892 KB
testcase_30.txt 4 ms 256 KB
testcase_31.txt 342 ms 5232 KB
testcase_32.txt 325 ms 6512 KB
testcase_33.txt 350 ms 4592 KB
testcase_34.txt 329 ms 5104 KB
testcase_35.txt 314 ms 5744 KB
testcase_36.txt 319 ms 6000 KB
testcase_37.txt 331 ms 5744 KB
testcase_38.txt 314 ms 6256 KB
testcase_39.txt 316 ms 4720 KB
testcase_40.txt 347 ms 4720 KB