QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#215019#6547. Bansheeucup-team1766#TL 1ms3640kbC++231.4kb2023-10-15 02:22:042023-10-15 02:22:04

Judging History

你现在查看的是最新测评结果

  • [2023-10-15 02:22:04]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3640kb
  • [2023-10-15 02:22:04]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

struct building {
	long long l;
	int t;
};

void run() {
	int n, m; cin >> n >> m;
	vector<building> b(n);
	long long sum = 0;
	for (int i = 0; i < n; i++) {
		long long x;
		int h, s;
		cin >> b[i].l >> x >> h >> s;
		b[i].l = max(0ll, b[i].l - 6);
		b[i].t = (h+s+23)/24;
		sum += b[i].t;
	}

	auto can = [&](long double limit) {
		vector<building> b2(b);
		long long pos = 0;
		int banshees = m;
		for (int i = 0; i < n; i++) {
			limit -= (b2[i].l - pos) / (long double)5.25;
			pos = b2[i].l;
			long long damage = limit/.89;
			int total = b2[i].t;
			int sac = total/damage;
			banshees -= sac;
			total -= sac*damage;

			if (total > 0) {
				double limit2 = limit;
				long long pos2 = pos;
				limit2 -= total*.89;
				banshees -= 1;
				while (limit2 >= .89) {
					i++;
					if (i == n) break;
					limit2 -= (b2[i].l - pos2) / 5.25;
					pos2 = b2[i].l;
					damage = min((int)(limit2/.89), b2[i].t);
					b2[i].t -= damage;
					limit2 -= damage*.89;
				}
				i--;
			}
			if (banshees < 0) {
				return false;
			}
		}
		return true;
	};

	double low = 0, high = sum*.89 + b[n-1].l/5.25 + 2;
	while (high - low >= 1e-5) {
		double mid = (low+high)/2;
		//cout << low << ' ' << high << endl;
		if (can(mid)) {
			high = mid;
		} else {
			low = mid+ 1e-5;
		}
	}

	cout << fixed << setprecision(13) << low << '\n';
}

int main() {
	int t; cin >> t;
	while (t--) run();
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3640kb

input:

2
2 1
1 2 1 100
100 500 736 0
3 2
0 1 12 0
1 2 6 6
2 3 3 10

output:

49.9447591069267
1.7800059754944

result:

ok 2 numbers

Test #2:

score: -100
Time Limit Exceeded

input:

1
1 1
999999999999 1000000000000 1000000 1000000

output:


result: