結果
問題 | No.198 キャンディー・ボックス2 |
ユーザー |
![]() |
提出日時 | 2016-12-27 16:27:47 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 1,000 ms |
コード長 | 1,743 bytes |
コンパイル時間 | 1,725 ms |
コンパイル使用メモリ | 166,688 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-16 10:07:57 |
合計ジャッジ時間 | 2,531 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> #ifndef LOCAL_ #define fprintf if( false ) fprintf #endif // LOCAL_ #define dumpi(x1) fprintf(stderr, "#%s.%d (%s) = (%d)\n", __func__, __LINE__, #x1, x1); #define dumpii(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%d, %d)\n", __func__, __LINE__, #x1, #x2, x1, x2); #define dumpiii(x1, x2, x3) fprintf(stderr, "#%s.%d (%s, %s, %s) = (%d, %d, %d)\n", __func__, __LINE__, #x1, #x2, #x3, x1, x2, x3); #define dumpl(x1) fprintf(stderr, "#%s.%d (%s) = (%ld)\n", __func__, __LINE__, #x1, x1); #define dumpll(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%ld, %ld)\n", __func__, __LINE__, #x1, #x2, x1, x2); #define dumpd(x1) fprintf(stderr, "#%s.%d (%s) = (%lf)\n", __func__, __LINE__, #x1, x1); #define dumpdd(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%lf, %lf)\n", __func__, __LINE__, #x1, #x2, x1, x2); int b; int n; int xs[16]; long total; int max; long calc(long t) { long res = 0; for(int i = 0; i < n; ++i) { res += std::abs(t - xs[i]); } return t * n <= total and t <= max ? res : (1LL << 40) + t; } void init() { total += b; for(int i = 0; i < n; ++i) { total += xs[i]; max = std::max(max, xs[i]); } } int main() { scanf("%d", &b); scanf("%d", &n); for(int i = 0; i < (int)n; ++i) { scanf("%d", &xs[i]); } init(); double left = 0; double right = (1LL << 30); for(int i = 0; i < 10000; ++i) { // dumpdd(left, right); double c1 = left + (right - left) * 1.0 / 3.0; double c2 = left + (right - left) * 2.0 / 3.0; double x1 = calc(long(c1)); double x2 = calc(long(c2 + 1)); if( x1 <= x2 ) { right = c2; } else { left = c1; } } dumpdd(left, right); printf("%ld\n", long(calc(long(right + (1e-10))))); return 0; }