#465003 (C++14) No.1309 テスト

提出ソース

結果

問題	No.1309 テスト
ユーザー	QCFium
提出日時	2020-04-16 22:51:28
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	823 ms / 4,000 ms
コード長	6,203 bytes
コンパイル時間	2,401 ms
コンパイル使用メモリ	168,344 KB
実行使用メモリ	4,540 KB
最終ジャッジ日時	2023-10-11 04:00:12
合計ジャッジ時間	10,122 ms
ジャッジサーバーID （参考情報）	judge12 / judge15

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	216 ms 4,348 KB
testcase_01	AC	2 ms 4,348 KB
testcase_02	AC	1 ms 4,352 KB
testcase_03	AC	2 ms 4,352 KB
testcase_04	AC	1 ms 4,356 KB
testcase_05	AC	2 ms 4,356 KB
testcase_06	AC	1 ms 4,352 KB
testcase_07	AC	1 ms 4,348 KB
testcase_08	AC	1 ms 4,348 KB
testcase_09	AC	2 ms 4,352 KB
testcase_10	AC	1 ms 4,352 KB
testcase_11	AC	1 ms 4,348 KB
testcase_12	AC	2 ms 4,352 KB
testcase_13	AC	1 ms 4,348 KB
testcase_14	AC	2 ms 4,352 KB
testcase_15	AC	2 ms 4,348 KB
testcase_16	AC	1 ms 4,348 KB
testcase_17	AC	1 ms 4,352 KB
testcase_18	AC	2 ms 4,352 KB
testcase_19	AC	1 ms 4,352 KB
testcase_20	AC	1 ms 4,352 KB
testcase_21	AC	1 ms 4,348 KB
testcase_22	AC	2 ms 4,352 KB
testcase_23	AC	2 ms 4,352 KB
testcase_24	AC	2 ms 4,352 KB
testcase_25	AC	2 ms 4,352 KB
testcase_26	AC	1 ms 4,348 KB
testcase_27	AC	2 ms 4,352 KB
testcase_28	AC	1 ms 4,352 KB
testcase_29	AC	1 ms 4,348 KB
testcase_30	AC	2 ms 4,352 KB
testcase_31	AC	1 ms 4,356 KB
testcase_32	AC	2 ms 4,348 KB
testcase_33	AC	1 ms 4,352 KB
testcase_34	AC	1 ms 4,352 KB
testcase_35	AC	1 ms 4,356 KB
testcase_36	AC	2 ms 4,352 KB
testcase_37	AC	1 ms 4,352 KB
testcase_38	AC	2 ms 4,348 KB
testcase_39	AC	2 ms 4,348 KB
testcase_40	AC	2 ms 4,352 KB
testcase_41	AC	2 ms 4,352 KB
testcase_42	AC	2 ms 4,352 KB
testcase_43	AC	1 ms 4,356 KB
testcase_44	AC	2 ms 4,348 KB
testcase_45	AC	2 ms 4,352 KB
testcase_46	AC	4 ms 4,352 KB
testcase_47	AC	4 ms 4,352 KB
testcase_48	AC	4 ms 4,540 KB
testcase_49	AC	4 ms 4,348 KB
testcase_50	AC	3 ms 4,352 KB
testcase_51	AC	4 ms 4,348 KB
testcase_52	AC	3 ms 4,348 KB
testcase_53	AC	3 ms 4,348 KB
testcase_54	AC	4 ms 4,352 KB
testcase_55	AC	4 ms 4,348 KB
testcase_56	AC	3 ms 4,352 KB
testcase_57	AC	3 ms 4,352 KB
testcase_58	AC	4 ms 4,352 KB
testcase_59	AC	4 ms 4,352 KB
testcase_60	AC	4 ms 4,352 KB
testcase_61	AC	3 ms 4,352 KB
testcase_62	AC	3 ms 4,348 KB
testcase_63	AC	3 ms 4,352 KB
testcase_64	AC	3 ms 4,352 KB
testcase_65	AC	131 ms 4,348 KB
testcase_66	AC	291 ms 4,352 KB
testcase_67	AC	220 ms 4,352 KB
testcase_68	AC	199 ms 4,348 KB
testcase_69	AC	256 ms 4,352 KB
testcase_70	AC	333 ms 4,356 KB
testcase_71	AC	759 ms 4,352 KB
testcase_72	AC	823 ms 4,352 KB
testcase_73	AC	674 ms 4,356 KB
testcase_74	AC	198 ms 4,352 KB
testcase_75	AC	116 ms 4,352 KB
testcase_76	AC	119 ms 4,352 KB
testcase_77	AC	11 ms 4,348 KB
testcase_78	AC	2 ms 4,348 KB
testcase_79	AC	1 ms 4,348 KB
testcase_80	AC	1 ms 4,352 KB
testcase_81	AC	1 ms 4,348 KB
testcase_82	AC	1 ms 4,348 KB
testcase_83	AC	2 ms 4,352 KB
testcase_84	AC	450 ms 4,352 KB
testcase_85	AC	259 ms 4,352 KB
testcase_86	AC	151 ms 4,348 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

typedef int64_t s64;
typedef uint64_t u64;

int n;
s64 max;
#define INF 1000000000000000000

namespace Fast {
	// max of sum of an array consisting of exactly all_num integers each in [min, max]
	//   that has exactly mode_num modes
	//      and they appear exactly mode_freq times each
	//      and sum of them(unique ones) equals to mode_sum
	// -INF if no such array exists
	// O(1)
	s64 calc(int mode_num, s64 mode_sum, int mode_freq, int min, int max, int all_num) {
		assert(mode_freq > 1);
		int other = all_num - mode_num * mode_freq;
		assert(other >= 0);
		if (!mode_num) {
			if (!mode_sum) {
				int other_block = other / (mode_freq - 1);
				int other_leftover = other % (mode_freq - 1);
				if (other_block + !!other_leftover > max - min + 1) return -INF;
				return (s64) other_block * (max + max - other_block + 1) / 2 * (mode_freq - 1) +
					(s64) other_leftover * (max - other_block);
			}
			return -INF; // invalid
		}
		if (max - min + 1 < mode_num) return -INF;
		s64 adding = mode_sum - (s64) mode_num * (min + min + mode_num - 1) / 2;
		if (adding < 0) return -INF;
		if ((s64) mode_num * (max + max - mode_num + 1) / 2 < mode_sum) return -INF;
		int other_block = other / (mode_freq - 1);
		int other_leftover = other % (mode_freq - 1);
		if (other_block && !other_leftover) other_block--, other_leftover = mode_freq - 1;
		if (other_block + !!other_leftover + mode_num > max - min + 1) return -INF;
		int default_clearance = max - min + 1 - (other_block + !!other_leftover + mode_num);
		int slide = adding / mode_num - default_clearance;
		s64 sum = mode_sum * mode_freq + (s64) other_block * (max + max - other_block + 1) / 2 * (mode_freq - 1)
			+ (s64) other_leftover * (max - other_block);
		if (slide > 0) {
			sum -= (other_leftover + (s64) (mode_freq - 1) * (slide - 1)) * mode_num;
			sum -= adding % mode_num * (mode_freq - 1);
		} else if (!slide) sum -= adding % mode_num * other_leftover;
		return sum;
	}
	s64 get_candidate(int mode_num, int mode_freq, int max, int all_num) {
		assert(mode_freq > 1);
		int other = all_num - mode_num * mode_freq;
		assert(other >= 0);
		if (!mode_num) return 0;
		
		int other_used = other / (mode_freq - 1);
		if (other % (mode_freq - 1)) other_used++;
		
		return (s64) (max - other_used + max - other_used - mode_num + 1) * mode_num / 2;
	}
	// max of sum of a non-decreasing array *a* consisting of exactly n integers each in [0, max] such that
	//   its median is *median* and it occupies exactly a[median_l, median_r)
	//   and there are exactly *left* modes in a[0, median_l) and exactly *right* modes in a[median_r, n)
	//     and their unique sum equals to mode_all_sum(the median itself as a mode does not count)
	//     and they appear exactly *freq* times each
	// -1 if no such array exists
	// O(1)
	s64 solve_sub(int median, int median_l, int median_r, int freq, s64 mode_all_sum, int left, int right) {
		s64 lower = 0, upper = mode_all_sum; // lower and upper bound(both inclusive) of sum of modes on the left side
		lower = std::max(lower, (s64) (left - 1) * left / 2);
		upper = std::min(upper, (s64) (median - 1 + median - left) * left / 2);
		lower = std::max(lower, mode_all_sum - (s64) (max + max - right + 1) * right / 2);
		upper = std::min(upper, mode_all_sum - (s64) (median + 1 + median + right) * right / 2);
		
		std::vector<s64> candidates{lower, upper};
		candidates.push_back(get_candidate(left, freq, median - 1, median_l));
		candidates.push_back(candidates.back() + left);
		candidates.push_back(mode_all_sum - get_candidate(right, freq, max, n - median_r));
		candidates.push_back(candidates.back() - right);
		s64 res = -1;
		for (auto left_sum : candidates) if (left_sum >= lower && left_sum <= upper) {
			s64 cur = (s64) (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, max, n - median_r);
			res = std::max(res, cur);
		}
		return res;
	}
	s64 run(int median, int mode) {
		assert(n & 1);
		int half = n / 2;
		int upper = max - median;
		s64 res = -1;
		// freq == 1
		if (median >= half && median + half <= max) {
			s64 min_sum = median + (s64) (half - 1) * half / 2 + (s64) (median + 1 + median + half) * half / 2;
			s64 max_sum = median + (s64) (median - 1 + median - half) * half / 2 + (s64) (max + max - half + 1) * half / 2;
			if ((s64) mode * n >= min_sum && (s64) mode * n <= max_sum) res = mode * n;
		}
		for (int freq = 2; freq <= n; freq++) {
			for (int left = 0; left * freq <= half && left <= median; left++) {
				for (int right = 0; right * freq <= half && right <= upper; right++) {
					int median_l_min = left * freq;
					int median_l_max = std::min<s64>(half, left * freq + (s64) (median - left) * (freq - 1));
					int median_r_max = n - right * freq;
					int median_r_min = std::max<s64>(half + 1, n - right * freq - (s64) (upper - right) * (freq - 1));
					assert(median_l_min <= median_l_max);
					assert(median_r_min <= median_r_max);
					if (left || right) { // don't use median as (one of) mode(s)
						s64 mode_all_sum = (s64) mode * (left + right);
						int median_r = median_r_min;
						int median_l = std::max(median_l_min, median_r - (freq - 1));
						if (median_l <= half) {
							assert(median_r > half);
							res = std::max(res, solve_sub(median, median_l, median_r, freq, mode_all_sum, left, right));
						}
					}
					{ // use median as (one of) mode(s)
						median_l_min = std::max(median_l_min, median_r_min - freq);
						median_l_max = std::min(median_l_max, median_r_max - freq);
						if (median_l_max >= median_l_min) {
							int median_l = median_l_min;
							assert(median_l <= half);
							assert(median_l + freq > half);
							s64 mode_all_sum = (s64) mode * (left + right + 1) - median;
							res = std::max(res, solve_sub(median, median_l, median_l + freq, freq, mode_all_sum, left, right));
						}
					}
				}
			}
		}
		return res;
	}
};

int main() {
	for (int i = 0; i < 10; i++) {
		n = ri();
		max = ri();
		int median = ri();
		int mode = ri();
		printf("%" PRId64 "\n", Fast::run(median, mode));
	}
	return 0;
}

yukicoder

結果

テストケース

ソースコード