結果

問題 No.198 キャンディー・ボックス２
コンテスト
ユーザー f1b_maxbl00d
提出日時 2020-03-11 21:00:26
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 1,701 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,226 ms
コンパイル使用メモリ 123,552 KB
最終ジャッジ日時 2025-01-09 06:19:45
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 12 WA * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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 = 1e8;
	for (; left <= right; left++) {
		ans = min(ans, calc(left));
	}
	cout << ans << "\n";
	return 0;
}
0