QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#214413#6547. Bansheeucup-team1196#TL 0ms3984kbC++201.8kb2023-10-14 19:28:122023-10-14 19:28:12

Judging History

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

  • [2023-10-14 19:28:12]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3984kb
  • [2023-10-14 19:28:12]
  • 提交

answer

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

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


signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while(t--)
	{
		
		int n, m;
		cin >> n >> m;
		int rmax = 0;
		vector<array<int, 2>> a(n + 1), b;
		for (int i = 1; i <= n; i++ )
		{
			int l, r, h, s;
			cin >> l >> r >> h >> s;
			rmax = max(l, rmax);
			a[i] = {l, h + s};
		}
		sort(a.begin() + 1, a.end());
		b = a;
		double l = 0, r = 1e18;
		while(l < r - 1e-5)
		{
			double mid = (l + r) / 2;
			auto check = [&](double mid)
			{	
				a = b;
				if(max(1.0 * rmax - 6, 0.0) / 5.25 + 0.89 > mid) return false;
				int used = 0;
				for (int i = 1; i <= n; i++ )
				{
					auto [p, h] = a[i];
					if(a[i][1] <= 1e-6) continue;
					double havetime = mid - max(0.0, 1.0 * p - 6) / 5.25;
					int attacktime = havetime / 0.89;
					int need = (h + 23) / 24;
					int peo = need / attacktime;
					used += peo;
					a[i][1] -= 24 * peo * attacktime;
					if(a[i][1] <= 1e-6) continue;
					need = (a[i][1] + 23) / 24;
					int attackcnt = 0;
					attackcnt += need;
					for(int j = i + 1 ; j <= n; j++ )
					{
						double havetime = mid - max(0.0, 1.0 * a[j][0] - 6) / 5.25;
						int attacktime = havetime / 0.89;
						int need = (a[j][1] + 23) / 24;
						if(attackcnt + need > attacktime)
						{
							a[j][1] -= max(0ll, (attacktime - attackcnt) * 24);
							break;
						}else{
							attackcnt += need;
							a[j][1] = 0;
							i = j;
						}
					}
					used++;	 
				}	
				if(used <= m) return true;
				else return false;
			};
			if(check(mid))
			{
				r = mid;
			}else{
				l = mid;
			}
		}
		cout << fixed << setprecision(10);
		cout << l << "\n";
	}
	return 0;	
} 

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3984kb

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.9447617218
1.7799934165

result:

ok 2 numbers

Test #2:

score: -100
Time Limit Exceeded

input:

1
1 1
999999999999 1000000000000 1000000 1000000

output:


result: