QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#95873#4392. BowcraftxuzhihaodedieAC ✓160ms4012kbC++14880b2023-04-12 10:37:412023-04-12 10:37:42

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-12 10:37:42]
  • 评测
  • 测评结果:AC
  • 用时:160ms
  • 内存:4012kb
  • [2023-04-12 10:37:41]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
const int mod=998244353;
const int N=2e5+100;
int k,a,b;
struct node {
	int a,b;
	double val;
}f[N];
bool cmp(node a,node b) {
	return a.val<b.val;
}
void solve(){
	cin>>k>>a>>b;
	int cnt=0;
	for(int i=0;i<a;i++) {
		for(int j=0;j<b;j++) {
			f[++cnt].a=i;
			f[cnt].b=j;
			if(i>0) f[cnt].val=(a*j-i*j)*1.0/(i*b);
			else f[cnt].val=1e18;
		}
	}
	vector<double> dp(k+10,0);
	//cout<<cnt<<endl;
	sort(f+1,f+cnt+1,cmp);
	for(int i=1;i<=k;i++) {
		dp[i]=1e20;
		double s1=0,s2=0;
		for(int j=1;j<=cnt;j++) {
			s1+=(f[j].a*1.0/a+f[j].b*1.0/b-f[j].a*1.0/a*f[j].b*1.0/b);
			s2+=(1.0-f[j].a*1.0/a);
			dp[i]=min(dp[i],(a*b+dp[i-1]*s1)*1.0/(j-s2));
		}
	}
	printf("%.3lf\n",dp[k]);
}
signed main() {
	int T;
	cin>>T;
	while(T--) {
		solve();
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 160ms
memory: 4012kb

input:

10
996 99 66
904 99 86
609 85 57
729 63 57
617 78 72
751 81 89
952 93 94
791 58 66
726 94 75
1000 100 100

output:

77416.113
75591.341
35314.209
48508.448
40062.330
58921.716
85820.717
59676.753
51117.885
93950.049

result:

ok 10 lines