結果

問題 No.1309 テスト
コンテスト
ユーザー QCFium
提出日時 2020-04-28 16:24:46
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 6,169 bytes
コンパイル時間 1,820 ms
コンパイル使用メモリ 171,028 KB
実行使用メモリ 10,268 KB
最終ジャッジ日時 2024-09-13 03:27:10
合計ジャッジ時間 19,589 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 69 TLE * 1 -- * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

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

// TLE expected

typedef int64_t s64;
typedef uint64_t u64;

int n;
int 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
		}
		assert(max - min + 1 >= mode_num);
		s64 adding = mode_sum - (s64) mode_num * (min + min + mode_num - 1) / 2;
		assert(adding >= 0);
		assert((s64) mode_num * (max + max - mode_num + 1) / 2 >= mode_sum);
		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<s64>(lower, (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 + (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 = (s64) mode * n;
		}
		for (int freq = 2; freq <= n; freq++) {
			for (int left = 0; left <= (n - 1) / 2; left++) {
				for (int right = 0; right <= (n - 1) / 2; 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));
					if (median_l_min > median_l_max) continue;
					if (median_r_min > median_r_max) continue;
					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;
}
0