結果

問題 No.198 キャンディー・ボックス２
ユーザー f1b_maxbl00df1b_maxbl00d
提出日時 2020-03-11 21:02:14
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 1,702 bytes
コンパイル時間 1,179 ms
コンパイル使用メモリ 127,528 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-08-10 01:40:46
合計ジャッジ時間 2,250 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 1 ms
4,376 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 2 ms
4,376 KB
testcase_12 AC 1 ms
4,376 KB
testcase_13 AC 1 ms
4,376 KB
testcase_14 AC 1 ms
4,376 KB
testcase_15 AC 1 ms
4,376 KB
testcase_16 AC 2 ms
4,376 KB
testcase_17 AC 2 ms
4,376 KB
testcase_18 AC 2 ms
4,380 KB
testcase_19 AC 2 ms
4,380 KB
testcase_20 AC 2 ms
4,376 KB
testcase_21 AC 2 ms
4,380 KB
testcase_22 AC 1 ms
4,380 KB
testcase_23 AC 1 ms
4,376 KB
testcase_24 AC 1 ms
4,380 KB
testcase_25 AC 1 ms
4,376 KB
testcase_26 AC 1 ms
4,380 KB
testcase_27 AC 2 ms
4,380 KB
testcase_28 AC 1 ms
4,380 KB
testcase_29 AC 1 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <random>
#include <functional>
#include <stack>
#include <iomanip>
#include <cassert>
//#include <boost/multiprecision/cpp_int.hpp>
#include <complex>
#include <cstdio>
#include <list>

//< in.txt > out.txt
using namespace std;
//std::ios::sync_with_stdio(false);
//std::cin.tie(0);
const long long MOD = 1e9 + 7;
typedef long long LL;
typedef long double LD;
typedef pair<LL, LL> PLL;
typedef pair<LD, LL> PDL;
typedef pair<LD, LD> PDD;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
//typedef boost::multiprecision::cpp_int bigint;

template<class T>
void in(T& x) {
	cin >> x;
}

template<class T1, class T2>
void in(pair<T1, T2>& p) {
	in(p.first);
	in(p.second);
}

template<class T>
void in(vector<T>& v, LL st = -1, LL en = -1) {
	if (st == -1) {
		st = 0;
		en = v.size() - 1;
	}
	for (LL n = st; n <= en; n++) {
		in(v[n]);
	}
}

LL B, N;
VLL A;

LL calc(LL c) {
	LL ans = 0;
	for (LL n = 0; n < N; n++) {
		ans += abs(A[n] - c);
	}
	return ans;
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	cin >> B >> N;
	A.resize(N);
	in(A);
	LL SUM = 0;
	for (LL n = 0; n < N; n++)SUM += A[n];
	LL left = 0, right = (SUM + B) / N;
	while (right - left > 2) {
		LL c1 = (left * 2 + right) / 3;
		LL c2 = (left + right * 2) / 3;
		LL f1 = calc(c1);
		LL f2 = calc(c2);
		if (f1 < f2)right = c2;
		else left = c1;
	}
	LL ans = 1e10;
	for (; left <= right; left++) {
		ans = min(ans, calc(left));
	}
	cout << ans << "\n";
	return 0;
}
0