結果

問題 No.21 平均の差
ユーザー DrafearDrafear
提出日時 2016-01-18 02:55:56
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 802 bytes
コンパイル時間 1,195 ms
コンパイル使用メモリ 162,692 KB
実行使用メモリ 10,016 KB
最終ジャッジ日時 2024-09-19 20:22:02
合計ジャッジ時間 7,659 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 6 ms
6,940 KB
testcase_02 AC 20 ms
6,940 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 TLE -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

int ans = 0;
vector<int> g;
vector<int> v;
int N, K;
void dfs(int n) {
	if (n == N) {
		vector<int> cnt(K, 0), sum(K, 0);
		for (int i = 0; i < g.size(); ++i) {
			cnt[g[i]]++;
			sum[g[i]] += v[i];
		}
		for (int i = 0; i < K; ++i) {
			if (cnt[i] == 0) return;
		}
		int m = 0, M = 0;
		for (int i = 0; i < K; ++i) {
			if (sum[i]*cnt[m] < sum[m]*cnt[i]) {
				m = i;
			}
			if (sum[i]*cnt[M] > sum[M]*cnt[i]) {
				M = i;
			}
		}
		int den = sum[M]*cnt[m]-sum[m]*cnt[M];
		int num = cnt[M]*cnt[m];
		ans = max(ans, (den+num-1)/num);
	}
	else {
		for (int i = 0; i < K; ++i) {
			g[n] = i;
			dfs(n+1);
		}
	}
}
int main() {
	cin >> N >> K;
	v.resize(N); g.resize(N);
	for (int i = 0; i < N; ++i) {
		cin >> v[i];
	}
	dfs(0);
	cout << ans << endl;
}
0