結果
| 問題 | No.1309 テスト |
| ユーザー |
 QCFium
|
| 提出日時 | 2020-06-01 01:22:00 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 3,941 bytes |
| コンパイル時間 | 339 ms |
| コンパイル使用メモリ | 82,112 KB |
| 実行使用メモリ | 206,644 KB |
| 最終ジャッジ日時 | 2024-09-13 03:30:48 |
| 合計ジャッジ時間 | 40,424 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1,286 ms
206,644 KB |
| testcase_01 | AC | 49 ms
61,924 KB |
| testcase_02 | AC | 40 ms
53,172 KB |
| testcase_03 | AC | 39 ms
55,036 KB |
| testcase_04 | AC | 39 ms
53,576 KB |
| testcase_05 | AC | 41 ms
53,076 KB |
| testcase_06 | AC | 40 ms
53,344 KB |
| testcase_07 | AC | 40 ms
53,552 KB |
| testcase_08 | AC | 40 ms
53,928 KB |
| testcase_09 | AC | 40 ms
54,860 KB |
| testcase_10 | AC | 40 ms
53,884 KB |
| testcase_11 | AC | 41 ms
54,784 KB |
| testcase_12 | AC | 41 ms
54,484 KB |
| testcase_13 | AC | 40 ms
53,376 KB |
| testcase_14 | AC | 41 ms
53,340 KB |
| testcase_15 | AC | 41 ms
55,252 KB |
| testcase_16 | AC | 41 ms
53,348 KB |
| testcase_17 | AC | 41 ms
55,076 KB |
| testcase_18 | AC | 42 ms
54,480 KB |
| testcase_19 | AC | 41 ms
54,664 KB |
| testcase_20 | AC | 41 ms
53,896 KB |
| testcase_21 | AC | 42 ms
54,668 KB |
| testcase_22 | AC | 41 ms
53,792 KB |
| testcase_23 | AC | 41 ms
54,192 KB |
| testcase_24 | AC | 41 ms
55,104 KB |
| testcase_25 | AC | 44 ms
59,552 KB |
| testcase_26 | AC | 45 ms
60,224 KB |
| testcase_27 | AC | 40 ms
54,876 KB |
| testcase_28 | AC | 40 ms
54,668 KB |
| testcase_29 | AC | 40 ms
52,888 KB |
| testcase_30 | AC | 41 ms
54,988 KB |
| testcase_31 | AC | 40 ms
54,080 KB |
| testcase_32 | AC | 40 ms
54,104 KB |
| testcase_33 | AC | 44 ms
61,236 KB |
| testcase_34 | AC | 39 ms
53,672 KB |
| testcase_35 | AC | 41 ms
54,176 KB |
| testcase_36 | AC | 40 ms
54,328 KB |
| testcase_37 | AC | 42 ms
54,712 KB |
| testcase_38 | AC | 39 ms
53,792 KB |
| testcase_39 | AC | 41 ms
54,572 KB |
| testcase_40 | AC | 43 ms
58,944 KB |
| testcase_41 | AC | 41 ms
53,576 KB |
| testcase_42 | AC | 42 ms
54,668 KB |
| testcase_43 | AC | 43 ms
53,912 KB |
| testcase_44 | AC | 40 ms
53,288 KB |
| testcase_45 | AC | 141 ms
77,316 KB |
| testcase_46 | AC | 366 ms
79,904 KB |
| testcase_47 | AC | 380 ms
82,032 KB |
| testcase_48 | AC | 363 ms
81,072 KB |
| testcase_49 | AC | 361 ms
80,024 KB |
| testcase_50 | AC | 223 ms
78,296 KB |
| testcase_51 | AC | 285 ms
78,672 KB |
| testcase_52 | AC | 259 ms
80,556 KB |
| testcase_53 | AC | 322 ms
79,644 KB |
| testcase_54 | AC | 362 ms
81,500 KB |
| testcase_55 | AC | 371 ms
79,796 KB |
| testcase_56 | AC | 289 ms
79,536 KB |
| testcase_57 | AC | 253 ms
79,608 KB |
| testcase_58 | AC | 346 ms
79,924 KB |
| testcase_59 | AC | 417 ms
81,272 KB |
| testcase_60 | AC | 276 ms
78,432 KB |
| testcase_61 | AC | 265 ms
79,240 KB |
| testcase_62 | AC | 289 ms
80,236 KB |
| testcase_63 | AC | 344 ms
79,624 KB |
| testcase_64 | AC | 400 ms
81,100 KB |
| testcase_65 | AC | 2,191 ms
103,956 KB |
| testcase_66 | AC | 3,808 ms
121,940 KB |
| testcase_67 | TLE | - |
| testcase_68 | AC | 3,496 ms
121,036 KB |
| testcase_69 | AC | 1,703 ms
88,456 KB |
| testcase_70 | AC | 3,715 ms
118,660 KB |
| testcase_71 | AC | 3,552 ms
95,532 KB |
| testcase_72 | TLE | - |
| testcase_73 | -- | - |
| testcase_74 | -- | - |
| testcase_75 | -- | - |
| testcase_76 | -- | - |
| testcase_77 | -- | - |
| testcase_78 | -- | - |
| testcase_79 | -- | - |
| testcase_80 | -- | - |
| testcase_81 | -- | - |
| testcase_82 | -- | - |
| testcase_83 | -- | - |
| testcase_84 | -- | - |
| testcase_85 | -- | - |
| testcase_86 | -- | - |
ソースコード
INF = 1000000000000000000 def calc(mode_num, mode_sum, mode_freq, lower, upper, all_num) : other = all_num - mode_num * mode_freq if not mode_num : if not mode_sum : other_block = other // (mode_freq - 1) other_leftover = other % (mode_freq - 1) if other_block + (1 if other_leftover else 0) > upper - lower + 1 : return -INF return other_block * (upper + upper - other_block + 1) // 2 * (mode_freq - 1) + \ other_leftover * (upper - other_block) return -INF adding = mode_sum - mode_num * (lower + lower + mode_num - 1) // 2 other_block = other // (mode_freq - 1) other_leftover = other % (mode_freq - 1) if other_block and not other_leftover : other_block -= 1 other_leftover = mode_freq - 1 if other_block + (1 if other_leftover else 0) + mode_num > upper - lower + 1 : return -INF default_clearance = upper - lower + 1 - (other_block + (1 if other_leftover else 0) + mode_num) slide = adding // mode_num - default_clearance sum = mode_sum * mode_freq + other_block * (upper + upper - other_block + 1) // 2 * (mode_freq - 1) + \ other_leftover * (upper - other_block) if slide > 0 : sum -= (other_leftover + (mode_freq - 1) * (slide - 1)) * mode_num sum -= adding % mode_num * (mode_freq - 1) elif not slide : sum -= adding % mode_num * other_leftover return sum def get_candidate(mode_num, mode_freq, upper, all_num) : other = all_num - mode_num * mode_freq if not mode_num : return 0 other_used = other // (mode_freq - 1) if other % (mode_freq - 1) : other_used += 1 return (upper - other_used + upper - other_used - mode_num + 1) * mode_num // 2 def solve_sub(median, median_l, median_r, freq, mode_all_sum, left, right) : lower = 0 upper = mode_all_sum lower = max(lower, (left - 1) * left // 2) upper = min(upper, (median - 1 + median - left) * left // 2) lower = max(lower, mode_all_sum - (p + p - right + 1) * right // 2) upper = min(upper, mode_all_sum - (median + 1 + median + right) * right // 2) candidates = [lower, upper] candidates.append(get_candidate(left, freq, median - 1, median_l)) candidates.append(candidates[-1] + left) candidates.append(mode_all_sum - get_candidate(right, freq, p, n - median_r)) candidates.append(candidates[-1] - right) res = -1 for left_sum in candidates : if left_sum >= lower and left_sum <= upper : cur = (median_r - median_l) * median cur += calc(left, left_sum, freq, 0, median - 1, median_l) cur += calc(right, mode_all_sum - left_sum, freq, median + 1, p, n - median_r) res = max(res, cur) return res for testcnt in range(10) : n, p, median, mode = map(int, input().split()) half = n // 2 upper = p - median res = -1 if median >= half and median + half <= p : min_sum = median + (half - 1) * half // 2 + (median + 1 + median + half) * half // 2 max_sum = median + (median - 1 + median - half) * half // 2 + (p + p - half + 1) * half // 2; if mode * n >= min_sum and mode * n <= max_sum : res = mode * n for freq in range(2, n + 1) : for left in range(0, min(median, half // freq) + 1) : for right in range(0, min(upper, half // freq) + 1) : median_l_min = left * freq median_l_max = min(half, left * freq + (median - left) * (freq - 1)) median_r_max = n - right * freq median_r_min = max(half + 1, n - right * freq - (upper - right) * (freq - 1)) if left or right : mode_all_sum = mode * (left + right) median_r = median_r_min median_l = max(median_l_min, median_r - (freq - 1)) if median_l <= half : res = max(res, solve_sub(median, median_l, median_r, freq, mode_all_sum, left, right)) median_l_min = max(median_l_min, median_r_min - freq) median_l_max = min(median_l_max, median_r_max - freq) if median_l_max >= median_l_min : median_l = median_l_min mode_all_sum = mode * (left + right + 1) - median res = max(res, solve_sub(median, median_l, median_l + freq, freq, mode_all_sum, left, right)) print(res)