编号 题目名称 状态 分数 总时间 内存 代码 提交者 提交时间
#142 #6. 挖金矿 Accepted 100 136 ms 22076 K C++ / 889 B Sengxian 2016-11-14 14:22:23
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAX_N = 500 + 3, MAX_M = 500 + 3;
int n, m, a[MAX_N][MAX_M];
ll s[MAX_N][MAX_M];

inline bool judge(double x) {
	double sum = 0, mx = 0;
	for (int j = 0; j < m; ++j) {
		mx = s[1][j] - x;
		for (int i = 2; i <= n; ++i)
			mx = max(mx, s[i][j] - i * x);
		sum += mx;
	}
	return sum >= 0;
}

int main() {
	freopen("miner.in", "r", stdin);
	freopen("miner.out", "w", stdout);
	scanf("%d%d", &n, &m);
	
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			scanf("%d", &a[i][j]);

	// 列的前缀和
	for (int j = 0; j < m; ++j)
		for (int i = 0; i < n; ++i)
			s[i + 1][j] = s[i][j] + a[i][j];
			
	double l = 0, r = 1e9;
	// 二分答案
	for (int i = 0; i < 50; ++i) {
		double mid = (l + r) / 2;
		if (judge(mid)) l = mid;
		else r = mid;
	}
	printf("%.4lf\n", l);
	return 0;
}
测试点 #1
Accepted
得分:100
用时:0 ms
内存:22076 KiB

输入文件

5 5
93 64 77 82 24
23 72 68 83 5
63 64 50 29 32
16 51 87 20 58
13 43 89 99 62
期望输出
71.7273
你的输出
71.7273

测试点 #2
Accepted
得分:100
用时:0 ms
内存:22076 KiB

输入文件

5 5
66 7 51 77 79
80 21 43 56 2
66 78 26 85 12
30 48 27 79 28
58 94 78 96 66
期望输出
67.6000
你的输出
67.6000

测试点 #3
Accepted
得分:100
用时:0 ms
内存:22076 KiB

输入文件

5 5
87 60 8 75 58
69 92 17 72 68
95 51 89 37 6
42 55 35 67 39
46 49 38 72 79
期望输出
68.4444
你的输出
68.4444

测试点 #4
Accepted
得分:100
用时:0 ms
内存:22076 KiB

输入文件

5 5
66 81 25 95 28
90 82 87 97 8
97 65 100 13 88
19 7 38 59 96
95 1 50 29 19
期望输出
77.0909
你的输出
77.0909

测试点 #5
Accepted
得分:100
用时:0 ms
内存:22076 KiB

输入文件

10 1
73509340
361478726
543671719
530865930
759028649
4359498
482449647
124693829
152503822
600919141
期望输出
453710872.8000
你的输出
453710872.8000

测试点 #6
Accepted
得分:100
用时:1 ms
内存:22076 KiB

输入文件

100 1
263925408
458705911
700430774
842479195
32037307
62349082
339998691
28581023
356499733
124999855
113523363
2981967...
期望输出
566385322.0000
你的输出
566385322.0000

测试点 #7
Accepted
得分:100
用时:1 ms
内存:22076 KiB

输入文件

300 1
609060230
75059602
612589212
446078234
809295502
783341227
542138514
608969420
992155592
566286520
109605368
71265...
期望输出
609060230.0000
你的输出
609060230.0000

测试点 #8
Accepted
得分:100
用时:1 ms
内存:22076 KiB

输入文件

300 1
263485035
533055604
294698148
576803676
128235063
820389559
449525025
946028187
347631370
292187018
95428108
99864...
期望输出
531850724.3226
你的输出
531850724.3226

测试点 #9
Accepted
得分:100
用时:68 ms
内存:22076 KiB

输入文件

500 500
729615644 63395319 576058074 743120950 237332921 814255094 481509048 329790464 637192712 435944004 452088215 878...
期望输出
631234990.4889
你的输出
631234990.4889

测试点 #10
Accepted
得分:100
用时:65 ms
内存:22076 KiB

输入文件

500 500
336213499 777863894 189829139 901207449 853507973 850154901 428828053 6322500 785731170 470168824 129054485 5227...
期望输出
621927748.1708
你的输出
621927748.1708