結果

問題 No.3604 Min of Max of Div of Sum
コンテスト
ユーザー pengin_2000
提出日時 2026-07-31 21:46:27
言語 C
(gcc 15.2.0)
コンパイル:
gcc-15 -O2 -DONLINE_JUDGE -o a.out _filename_ -lm
実行:
./a.out
結果
AC  
実行時間 92 ms / 2,000 ms
+ 574µs
コード長 1,072 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 421 ms
コンパイル使用メモリ 39,552 KB
実行使用メモリ 6,528 KB
最終ジャッジ日時 2026-07-31 21:46:45
合計ジャッジ時間 3,319 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<stdio.h>
double a[100005];
double left_min[100005], right_max[100005];
int A[100005], B[100005];
long long int sa[100005], sb[100005];
int main()
{
	int n;
	scanf("%d", &n);
	int i, j;
	for (i = 0; i < n; i++)
		scanf("%d", &A[i]);
	for (i = 0; i < n; i++)
		scanf("%d", &B[i]);
	sa[0] = sb[0] = 0;
	for (i = 0; i < n; i++)
		sa[i + 1] = sa[i] + A[i];
	for (i = 0; i < n; i++)
		sb[i + 1] = sb[i] + B[i];
	double min, mid, max;
	min = 0;
	max = 1e18;
	int f;
	for (j = 0; j < 200; j++)
	{
		mid = (max + min) / 2;
		for (i = 0; i <= n; i++)
			a[i] = sa[i] - sb[i] * mid;
		left_min[0] = a[0];
		for (i = 1; i <= n; i++)
		{
			if (left_min[i - 1] > a[i])
				left_min[i] = a[i];
			else
				left_min[i] = left_min[i - 1];
		}
		right_max[n] = a[n];
		for (i = n - 1; i >= 0; i--)
		{
			if (right_max[i + 1] < a[i])
				right_max[i] = a[i];
			else
				right_max[i] = right_max[i + 1];
		}
		f = 0;
		for (i = 0; i < n; i++)
			if (left_min[i] > right_max[i + 1])
				f++;
		if (f > 0)
			max = mid;
		else
			min = mid;
	}
	printf("%.20lf\n", min);
	return 0;
}
0