QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#440246	#2629. Let's Win the Election	hansiyuan	77	80ms	5948kb	C++14	896b	2024-06-13 14:17:52	2024-06-13 14:17:54

Judging History

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

[2024-06-13 14:17:54]
评测

测评结果：77
用时：80ms
内存：5948kb

查看

[2024-06-13 14:17:52]
提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N=505;
int n,m;
struct nd{
	int a,b;
	bool operator < (const nd &y)const{
		if(b==y.b) return a<y.a;
		return b<y.b;
	}
}s[N];
int t[N],res[N];
double f[N][N],ans=1e9;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&s[i].a,&s[i].b);
		if(s[i].b==-1) s[i].b = 1e9;
	}
	sort(s+1,s+n+1);
	for(int i=m;i>=1;i--){
		for(int j=i;j<=n;j++)
			t[j-i+1] = s[j].a;
		sort(t+1,t+(n-i+1)+1);
		for(int j=1;j<=m-i+1;j++)
			res[i] += t[j];
	}
	for(int i=1;i<=m;i++)
		f[0][i]=1e9;
	for(int k=0;k<=m;k++){
		for(int i=1;i<=m;i++){
			for(int j=0;j<=k;j++){
				f[i][j] = f[i-1][j] + (double)s[i].a/(k+1);
				if(j && s[i].b!=1e9)
					f[i][j] = min(f[i][j],f[i-1][j-1]+(double)s[i].b/j);
			}
			ans = min(ans,f[i][k]+(double)res[i+1]/(k+1));
		}
	}
	printf("%.10lf\n",ans);
	return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5

Accepted

Test #1:

score: 5

Accepted

time: 1ms

memory: 3964kb

input:

1
1
729 -1

output:

729.0000000000

result:

ok error = 0.000000000

Test #2:

score: 5

Accepted

time: 0ms

memory: 3956kb

input:

output:

300.0000000000

result:

ok error = 0.000000000

Test #3:

score: 5

Accepted

time: 0ms

memory: 3892kb

input:

output:

1140.0000000000

result:

ok error = 0.000000000

Test #4:

score: 5

Accepted

time: 1ms

memory: 3972kb

input:

output:

1059.0000000000

result:

ok error = 0.000000000

Test #5:

score: 5

Accepted

time: 1ms

memory: 4152kb

input:

output:

2580.0000000000

result:

ok error = 0.000000000

Test #6:

score: 5

Accepted

time: 0ms

memory: 4460kb

input:

output:

15729.0000000000

result:

ok error = 0.000000000

Test #7:

score: 5

Accepted

time: 9ms

memory: 4796kb

input:

output:

66687.0000000000

result:

ok error = 0.000000000

Test #8:

score: 5

Accepted

time: 26ms

memory: 5444kb

input:

output:

147876.0000000000

result:

ok error = 0.000000000

Test #9:

score: 5

Accepted

time: 58ms

memory: 5928kb

input:

output:

249562.0000000000

result:

ok error = 0.000000000

Test #10:

score: 5

Accepted

time: 21ms

memory: 5272kb

input:

output:

350000.0000000000

result:

ok error = 0.000000000

Subtask #2:

score: 5

Accepted

Test #11:

score: 5

Accepted

time: 1ms

memory: 3888kb

input:

1
1
791 791

output:

791.0000000000

result:

ok error = 0.000000000

Test #12:

score: 5

Accepted

time: 0ms

memory: 4476kb

input:

output:

341.0793145790

result:

ok error = 0.000000000

Test #13:

score: 5

Accepted

time: 2ms

memory: 4540kb

input:

output:

355.3422864151

result:

ok error = 0.000000000

Test #14:

score: 5

Accepted

time: 1ms

memory: 4476kb

input:

output:

940.6896888795

result:

ok error = 0.000000000

Test #15:

score: 5

Accepted

time: 28ms

memory: 5300kb

input:

output:

707.0462281505

result:

ok error = 0.000000000

Test #16:

score: 5

Accepted

time: 28ms

memory: 5268kb

input:

output:

982.1345592058

result:

ok error = 0.000000000

Test #17:

score: 5

Accepted

time: 20ms

memory: 5264kb

input:

output:

1956.1865688047

result:

ok error = 0.000000000

Test #18:

score: 5

Accepted

time: 77ms

memory: 5936kb

input:

output:

1043.2370845765

result:

ok error = 0.000000000

Test #19:

score: 5

Accepted

time: 71ms

memory: 5868kb

input:

output:

1370.7448905568

result:

ok error = 0.000000000

Test #20:

score: 5

Accepted

time: 62ms

memory: 5780kb

input:

output:

3138.9576298335

result:

ok error = 0.000000000

Subtask #3:

score: 0

Wrong Answer

Test #21:

score: 0

Wrong Answer

time: 0ms

memory: 3868kb

input:

output:

104.0000000000

result:

wrong answer read 104.000000000 but expected 51.000000000, error = 53.000000000

Subtask #4:

score: 0

Wrong Answer

Test #36:

score: 0

Wrong Answer

time: 0ms

memory: 3888kb

input:

output:

155.0000000000

result:

wrong answer read 155.000000000 but expected 112.000000000, error = 43.000000000

Subtask #5:

score: 33

Accepted

Test #61:

score: 33

Accepted

time: 1ms

memory: 3864kb

input:

output:

324.3333333333

result:

ok error = 0.000000000

Test #62:

score: 33

Accepted

time: 1ms

memory: 3968kb

input:

output:

1892.3205266955

result:

ok error = 0.000000000

Test #63:

score: 33

Accepted

time: 1ms

memory: 3964kb

input:

output:

646.3428571429

result:

ok error = 0.000000000

Test #64:

score: 33

Accepted

time: 1ms

memory: 4008kb

input:

output:

2424.8503110795

result:

ok error = 0.000000000

Test #65:

score: 33

Accepted

time: 0ms

memory: 4080kb

input:

output:

2866.6789228134

result:

ok error = 0.000000000

Test #66:

score: 33

Accepted

time: 0ms

memory: 4084kb

input:

output:

945.4370896389

result:

ok error = 0.000000000

Test #67:

score: 33

Accepted

time: 1ms

memory: 4152kb

input:

output:

984.3445000390

result:

ok error = 0.000000000

Test #68:

score: 33

Accepted

time: 0ms

memory: 4084kb

input:

output:

3132.9647579540

result:

ok error = 0.000000000

Test #69:

score: 33

Accepted

time: 1ms

memory: 4180kb

input:

output:

3152.9110642795

result:

ok error = 0.000000000

Test #70:

score: 33

Accepted

time: 1ms

memory: 4176kb

input:

output:

1227.6118437324

result:

ok error = 0.000000000

Test #71:

score: 33

Accepted

time: 2ms

memory: 4220kb

input:

output:

1732.0259229714

result:

ok error = 0.000000000

Test #72:

score: 33

Accepted

time: 1ms

memory: 4352kb

input:

output:

3448.0214158294

result:

ok error = 0.000000000

Test #73:

score: 33

Accepted

time: 0ms

memory: 4140kb

input:

output:

2854.2723304473

result:

ok error = 0.000000000

Test #74:

score: 33

Accepted

time: 1ms

memory: 4136kb

input:

output:

2704.4200840421

result:

ok error = 0.000000000

Test #75:

score: 33

Accepted

time: 1ms

memory: 4132kb

input:

output:

2421.8092932050

result:

ok error = 0.000000000

Test #76:

score: 33

Accepted

time: 0ms

memory: 4180kb

input:

output:

2114.6567973693

result:

ok error = 0.000000000

Test #77:

score: 33

Accepted

time: 1ms

memory: 4212kb

input:

output:

2666.0489753128

result:

ok error = 0.000000000

Test #78:

score: 33

Accepted

time: 1ms

memory: 4144kb

input:

output:

2807.7078472080

result:

ok error = 0.000000000

Test #79:

score: 33

Accepted

time: 1ms

memory: 4220kb

input:

output:

2610.9578556339

result:

ok error = 0.000000000

Test #80:

score: 33

Accepted

time: 1ms

memory: 4220kb

input:

output:

2656.8567465914

result:

ok error = 0.000000000

Subtask #6:

score: 11

Accepted

Test #81:

score: 11

Accepted

time: 80ms

memory: 5804kb

input:

output:

1767.1975007973

result:

ok error = 0.000000000

Test #82:

score: 11

Accepted

time: 80ms

memory: 5860kb

input:

output:

2763.3815674113

result:

ok error = 0.000000000

Test #83:

score: 11

Accepted

time: 79ms

memory: 5856kb

input:

output:

3763.0435188736

result:

ok error = 0.000000000

Test #84:

score: 11

Accepted

time: 76ms

memory: 5876kb

input:

output:

4840.5411729334

result:

ok error = 0.000000000

Test #85:

score: 11

Accepted

time: 80ms

memory: 5936kb

input:

output:

5820.4909981528

result:

ok error = 0.000000000

Test #86:

score: 11

Accepted

time: 79ms

memory: 5948kb

input:

output:

3946.9244817827

result:

ok error = 0.000000000

Test #87:

score: 11

Accepted

time: 79ms

memory: 5864kb

input:

output:

3878.5527203058

result:

ok error = 0.000000000

Subtask #7:

score: 23

Accepted

Test #88:

score: 23

Accepted

time: 1ms

memory: 4000kb

input:

output:

368.1297619048

result:

ok error = 0.000000000

Test #89:

score: 23

Accepted

time: 2ms

memory: 4072kb

input:

output:

2882.4745823040

result:

ok error = 0.000000000

Test #90:

score: 23

Accepted

time: 3ms

memory: 4460kb

input:

output:

641.5151181260

result:

ok error = 0.000000000

Test #91:

score: 23

Accepted

time: 3ms

memory: 4448kb

input:

output:

3543.8836038744

result:

ok error = 0.000000000

Test #92:

score: 23

Accepted

time: 13ms

memory: 4908kb

input:

output:

955.8861020681

result:

ok error = 0.000000000

Test #93:

score: 23

Accepted

time: 13ms

memory: 4876kb

input:

output:

4225.9687876561

result:

ok error = 0.000000000

Test #94:

score: 23

Accepted

time: 36ms

memory: 5368kb

input:

output:

1459.5140837496

result:

ok error = 0.000000000

Test #95:

score: 23

Accepted

time: 36ms

memory: 5308kb

input:

output:

4543.5172691461

result:

ok error = 0.000000000

Test #96:

score: 23

Accepted

time: 55ms

memory: 5664kb

input:

output:

1503.7968079258

result:

ok error = 0.000000000

Test #97:

score: 23

Accepted

time: 59ms

memory: 5676kb

input:

output:

4679.3552447889

result:

ok error = 0.000000000

Test #98:

score: 23

Accepted

time: 30ms

memory: 5336kb

input:

output:

3006.7652979011

result:

ok error = 0.000000000

Test #99:

score: 23

Accepted

time: 30ms

memory: 5208kb

input:

output:

3767.2089795903

result:

ok error = 0.000000000

Test #100:

score: 23

Accepted

time: 35ms

memory: 5204kb

input:

output:

3691.7046047957

result:

ok error = 0.000000000

Test #101:

score: 23

Accepted

time: 30ms

memory: 5232kb

input:

output:

3489.9814632569

result:

ok error = 0.000000000

Test #102:

score: 23

Accepted

time: 30ms

memory: 5280kb

input:

output:

3505.9720675481

result:

ok error = 0.000000000

Test #103:

score: 23

Accepted

time: 29ms

memory: 5344kb

input:

output:

3562.0854954342

result:

ok error = 0.000000000

Test #104:

score: 23

Accepted

time: 35ms

memory: 5256kb

input:

output:

3476.2567559925

result:

ok error = 0.000000000

Test #105:

score: 23

Accepted

time: 28ms

memory: 5272kb

input:

output:

350.0000000000

result:

ok error = 0.000000000